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

思路：

题目的主要信息：

在数组中，选取一组序列，使和最大
选取的数中，位置不能相邻
可以不选或是选一个数

方法一：递归（超时）
具体做法：
对于n个元素的数组，如果最后一个数字被选择了，则前一个数字必不会被选，那就是n-2的结果加上最后一个数字，如果最后一个数字没有被选择，则是n-1的结果，选取其中最大值即可。
由此将一个n的问题，划分成了n-1和n-2的子问题，因此可以用递归解决，返回点即是0和1的时候。
图片说明

class Solution {
public:
    long long subsequence(int n, vector<int>& array) {
        //0 和 1单独处理
        if(n == 0)
            return (long long)array[0];
        else if(n == 1)
            return max((long long)array[0], (long long)array[1]); 
        //选择子问题中的最大值
        return max(subsequence(n - 1, array), subsequence(n - 2, array) + (long long)array[n]);
    }
};

复杂度分析：

时间复杂度： $O(2^n)$ ，递推式子为 $T(n)=T(n-1)+T(n-2)$ ，树型递归
空间复杂度： $O(n)$ ，递归栈最大深度

方法二：动态规划
具体做法：
方法一中n的子问题有n-1和n-2，n-1的子问题又有n-2，因此越小规模的子问题就会有更多重复的计算，我们可以用一数组dp, $dp[i]$ 表示前i个数的最大子序列和，从0和1开始往上加，每次选取 $dp[i-1]$ 与 $dp[i - 2] + array[i]$ 之间的最大值。
方法二即是方法一的从下往上加，参考图同方法一。

class Solution {
public:
    long long subsequence(int n, vector<int>& array) {
        vector<long long> dp(n); //记录当前i个数字时，最大的子序列和
        //0和1单独讨论
        dp[0] = array[0];   
        dp[1] = max(dp[0], (long long)array[1]);
        for(int i = 2; i < n; i++)  //两种方式最大值
            dp[i] = max(dp[i - 1], (dp[i - 2] + (long long)array[i]));
        return dp[n - 1];
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(n)$ ，辅助数组dp