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

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

    if (n == 0) return 0;
    if (n == 1) return max(0, array[0]);
    long long ans;
    vector<long long> dp(n + 1);
    dp[1] = max(0, array[0]);

    for (int i = 1; i < n; i++)
    {
        //此时节点的最大值因该时max{当前节点值array[i]，当前节点值array[i]+隔点值,前i-1个最大值}

            long long  temp = max(array[i] + dp[i - 1], dp[i]);//array[i] + dp[i - 2]);
            dp[i + 1] = max((long long) array[i], temp);
    }
    return dp[n];
}

};