最大不相邻子序列和

​
看到这题，很容易观察到这是一个包含子问题的，直接dp。

题目要求是不相邻的子序列值。 什么样子会帮助满足最大呢？
1，序列包含尽可能多的数
2，序列包含尽可能大的数。
考虑不相邻的话，要不要加入第i个数，需要考虑的问题是它前一个i-1 要不要加入，至于i-2则不需要考虑，因为加入第i个数必然可以加入不相邻的i-2 。换句话说，你不会跳过3个数。
换成代码就是 dp[i+3] = max(dp[i+2], dp[i+1]+arr[i])

class Solution {
public:
    long long subsequence(int n, vector<int>& array) {
        // write code 
        long long dp1=0,dp2=0;
        for(auto& it : array) {
            long long dp3= max(dp1+it,dp2);
            dp1 = dp2;
            dp2 = dp3;
        }
        return dp2;
    }
};