题解 | #不相邻最大子序列和#

采用动态规划思路，定义数组dp来记录两种状态，dp长为n，宽为2：

• （1）dp[i][0]:不以array[i]为结尾的最大子序列和；
• （2）dp[i][1]:以array[i]为结尾的最大子序列和；

那么有以下转移方程：

• （1）dp[i][0] = max(dp[i-1][0], dp[i-1][1])
• （2）dp[i][1] = max(dp[i-1][0]+array[i], array[i]);

由于自带的max函数不能计算long long值，所以自己写了比较函数。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型vector 长度为n的数组
     * @return long长整型
     */
    long long subsequence(int n, vector<int>& array) {
        // write code here
        vector<vector<long long>> dp(n, vector<long long>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = array[0];
        long long res = bijiao(dp[0][0], dp[0][1]);
        
        for(int i=1; i<n; i++){
            dp[i][0] = bijiao(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = bijiao(dp[i-1][0], 0) + array[i];
            res = bijiao(res, dp[i][0]);
            res = bijiao(res, dp[i][1]);
        }
        
        return res;
    }
    
    long long bijiao(long long a, long long b){
        if(a > b){
            return a;
        }
        return b;
    }
    
};