题意整理：

本题实际上的要求就是从数组中选择一些数，要求这些数字不相邻，求能够得到的最大子序列和。
对于一个数字，如果它相邻的数字被选取，那么我们不能选取这个数字；如果它相邻的数字没有被选取，那么我们可以考虑选取或者不选取这个数字。
注意到一个问题，对于连续的三个数 ,在这三个数中，我们最少会选择一个数字，否则不是最优解。如果 被选取，那么已经选择了一个数；否则，我们肯定会在 中选择一个数字，如果没有的话，那么选择 能够让结果比不选择更大，而且不会与其他元素造成矛盾。对于数组第一个元素和第二个元素，两个元素必须要选择一个，否则同上可以推出此序列不是最优解：既额外选择第一个元素不会引出矛盾且能够让答案更大。

方法一：递归(超时）

核心思想：

由上述分析以及需要注意的点可以发现，对于一个数组 ，它的不相邻最大子序和必然为选择第一个元素后的情况和选择第二个元素后的情况，而且两个元素无法同时选取，所以可以拆分为子问题进行递归计算。在确定对一个元素 进行选取后，其右侧元素显然不能选取，而由上分析，对其后元素,中必须选择一个进行选取。所以递归的思路非常明确，既使用一个函数表示对矩阵中第 i 个元素进行选取，之后能够产生的最大子序和。选取一个元素后，递归的是选取其右侧第二和第三个元素两种情况，并返回较大值。

核心代码：

class Solution {
public:
    long long dfs(vector<int>& array, int p, int n) {
        if(p >= n) return 0;
        return array[p] + max(dfs(array, p + 2, n), dfs(array, p + 3, n));
    }

    long long subsequence(int n, vector<int>& array) {
        return max(dfs(array, 0, n), dfs(array, 1, n));
    }
};

复杂度分析：

时间复杂度：,对于每个元素都需要对其后两个元素进行递归，所以复杂度是指数级的。根据分析，相当于把问题拆分为选择第一个和第二个的子问题，由递归树可以知道复杂度为。
空间复杂度：，即为递归栈的最大深度。

方法二：动态规划

核心思想：

观察方法一的递归树可以发现超时的原因，下图给出递归树的一部分：

显然，方法一对很多状态进行了重复计算。此时可以利用动态规划，将计算过的结果存储起来，避免重复计算
具体实现：令表示对前 个数进行计算的最大子序和。对于 ，同方法一的分析可得转移方程,边界条件为,。

核心代码：

class Solution {
public:
    long long subsequence(int n, vector<int>& array) {
        if(n == 1) return array[0];
        vector<long long> dp(n);//表示对前i个元素的最大子序和
        dp[0] = array[0];//处理边界
        dp[1] = max(array[0], array[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 2] + array[i], dp[i - 1]);//进行转移
        }
        return dp[n - 1];
    }
};

复杂度分析：

时间复杂度：，只进行了一次遍历
空间复杂度：,使用了与原数组等长的dp数组

方法三：空间优化的动态规划

核心思想：

实际上可以只使用两个变量对子序和进行计算，表示对当前元素不选择的最大和，表示对当前元素选择的最大和，对 i 的分析直接处于循环中。

核心代码：

class Solution {
public:
    long long subsequence(int n, vector<int>& array) {
        if(n == 1) return array[0];
        //dp1表示不选择当前元素，dp1表示选择当前元素
        int dp1 = 0, dp2 = array[0], res = 0;
        for(int i = 1; i < n; ++i) {
            res = dp1;//记录上一轮不进行选择的情况
            dp1 = max(dp1, dp2);//不选择当前元素，所以可以上一轮选择或不选择都可以
            dp2 = array[i] + res;//选择当前元素，所以上一轮不能选择
        }
        return max(dp1, dp2);
    }
};

复杂度分析：

时间复杂度：，只进行了一次遍历
空间复杂度：,使用了常数个变量