一、原题
从数列A[0], A[1], A[2], ..., A[N-1]中选若干个数，要求相邻的数不能都选，也就是说如果选了A[i], 就不能选A[i-1]和A[i+1]。 求能选出的最大和。
1 <= N <= 100000, 1 <= A[i] <= 1000
例1：A = {2, 5, 2}，答案为5。
例2：A = {2, 5, 4}，答案为6。
二、思路
假设数组为：[1, 3, 5, 0, 9, 8, 4, 7]，逐一分析：
-
[1]：结果显而易见为1，此时选择了1； -
[1, 3]：结果显而易见为3，此时选择了3； -
[1, 3, 5]：分析5，如果选择5，则3不允许选，则1+5=6（1为第1步的最优解），如果不选择5，则结果为第2步的最优解3。综上则最优为6； -
[1, 3, 5, 0]：分析0，因为0选不选都一样，则最优为第3步最优解6； -
[1, 3, 5, 0, 9]：分析9，如果选择9，则0不能选，则6+9=15（6为第3步最优解），如果不选9，则最优为第4步最优解6。综上则最优为15； -
[1, 3, 5, 0, 9, 8]：分析8，如果选择8，则9不能选，则6+8=14（6为第4不最优解），如果不选8，则最优为第5步最优解15.综上则最优为15；
结合以上的推断，能够大概推断出状态dp[i]为以A[i]为结尾的数组的最大和。
对于一个数组的序列，分析其中的某一个A[i]：
- 若A[i-1]不在dp[i-1]的结果序列中，则表示A[i]允许被选中，最优结果肯定是A[i]+dp[i-1]；
- 若A[i-1]在dp[i-1]的结果序列中，则表示A[i-1]已被选中，如要选择A[i]则必须忽略A[i-1]，所以结果只能是dp[i-2]+A[i]，但此时最优结果可能落在dp[i-2]+A[i]和dp[i-1]中，选最优即可；
因此状态转移方程dp[i]=A[i-1]是否在dp[i-1]的结果序列中 ? max{dp[i-1], dp[i-2]+A[i]} : dp[i-1]+A[i]
其中“A[i-1]是否在dp[i-1]的结果序列中”意思是，例如[1, 3, 5]中，最大和为6，序列为[1, 5]则此时3不在该最大和的序列中；在[1, 3, 5, 0, 9]中，最大和为15，序列为[1, 5, 9]，此时5在最大和的序列中；
三、代码
class Solution {
public:
int getMax(int a, int b) {
return a > b ? a : b;
}
int maxSum(vector<int> &A) {
if (A.empty()) {
return 0;
}
int size = A.size();
int *dp = new int[size];
bool *used = new bool[size]; // 用于记录每一个字数字是否在dp[i-1]的结果序列中
for (int i = 0; i < size; ++i) {
if (i == 0) {
used[i] = true;
dp[i] = A[i];
} else {
if (used[i - 1]) { // 上一个在dp[i-1]的结果序列中：dp[i] = max{dp[i-1], dp[i-2]+A[i]}
dp[i] = getMax(A[i] + (i - 2 >= 0 ? dp[i - 2] : 0), dp[i - 1]);
used[i] = dp[i] != dp[i - 1];
} else { // 上一个不在dp[i-1]的结果序列中：dp[i] = dp[i-1]+A[i]
dp[i] = A[i] + dp[i - 1];
used[i] = true;
}
}
}
int res = dp[size - 1];
delete[] dp;
delete[] used;
return res;
}
};
