【牛客题霸题解】不相邻最大子序列和

表示区间 的不相邻最大子序列和，
那 就是我们要找的答案了。
如果取 的话， 就不能取了，这个情况下 的不相邻最大子序列和 为
如果不取 的话 ， 的不相邻最大子序列和 为
所以
c++

class Solution {
public:
    long long subsequence(int n, vector<int>& array) {
        vector<long long> dp(n);
        dp[0] = max(0,array[0]);
        dp[1] = max(dp[0],(long long)array[1]);
        for(int i = 2 ; i < n ; i++)
        {
            dp[i] = max(array[i]+dp[i-2],dp[i-1]);
        }
        return dp[n-1];
    }
};

java

import java.util.*;
public class Solution {
    public long subsequence (int n, int[] array) {
        long dp[] = new long[n];
        dp[0] = Math.max(0,array[0]);
        dp[1] = Math.max(dp[0],Long.valueOf(array[1]));
        for(int i = 2 ; i < n ; i++)
        {
            dp[i] = Math.max(array[i]+dp[i-2],dp[i-1]);
        }
        return dp[n-1];
    }
}

python

class Solution:
    def subsequence(self , n , array ):
        # write code here
        dp = [0]*n
        dp[0] = max(0,array[0])
        dp[1] = max(dp[0],array[1])
        for i in range(2,n):
            dp[i] = max(array[i]+dp[i-2],dp[i-1]);
        return dp[n-1];