题解 | #不相邻最大子序列和# 打家劫舍+符号应用+ 取下限！

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

        dp[0] = max(0, array[0]);
        dp[1] = max(dp[1], (long long) array[1]);
        
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i-2] + array[i], dp[i-1]);
        }
        return dp[n-1];
        // write code here
    }
};