Sicily1005. 最大和

一、原题

从数列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；
2. [1, 3]：结果显而易见为3，此时选择了3；
3. [1, 3, 5]：分析5，如果选择5，则3不允许选，则1+5=6（1为第1步的最优解），如果不选择5，则结果为第2步的最优解3。综上则最优为6；
4. [1, 3, 5, 0]：分析0，因为0选不选都一样，则最优为第3步最优解6；
5. [1, 3, 5, 0, 9]：分析9，如果选择9，则0不能选，则6+9=15（6为第3步最优解），如果不选9，则最优为第4步最优解6。综上则最优为15；
6. [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;
    }
};