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

从例子进行分析
3,[1,2,3]
在index = 0，有两种选择：
取 得到取值 1
不取 得到取值 0

 这个位置能拿到的最大收益就是1

在index = 1，也有两种选择：
取 （此时，由于相邻的两个下标是不能取的，因此，得到的值只能是 2 +（index = -1的最大收益）= 2
不取 那到目前位置（此时可能获得的收益就是index = 1的最大收益），取值就是 1

这个位置能拿到的最大收益就是2

在index = 2，也有两种选择：
取 此时得到的值就是 3 + （index = 0取，时得到的最大收益 = 1） = 4
不取 此时得到的值就是 0 + （index = 1取，时得到的最大收益 = 2） = 2

因此，最大收益就是4

另一个例子

4,[4,2,3,5]
index=0
不取 0
取 4
这个位置能拿到的最大收益就是4
index = 1
不取 4
取 2
这个位置能拿到的最大收益就是 4
index = 2
不取 4
取 4+3 = 7
这个位置能拿到的最大收益就是7

index = 3
不取 7
取 4+5 = 9
这个位置能拿到的最大收益就是9

代码如下：

    long long subsequence(int n, vector<int>& array) {
        // write code here
        int first = 0; //i-2的最大收益
        int second = 0; //i-1的最大收益
        int max_value = 0;
        for(int i = 0;i<array.size();i++){
            int temp_max = max(second, first + array[i]);
            max_value = max(temp_max, max_value);
            first = second;
            second = temp_max;
        }
        return max_value;
    }

再简化下：

    long long subsequence(int n, vector<int>& array) {
        // write code here
        int first = 0;
        int second = 0;
        for(int i = 0;i<array.size();i++){
            int temp_max = max(second, first + array[i]);
            first = second;
            second = temp_max;
        }
        return second;
    }