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

不相邻最大子序列和

动态规划

根据题目的描述可以很快明白这是一个 01 背包问题，根据前边已经计算好的前 i 个节点的结果判断是否选择当前节点。
状态转移方程：

dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i-1])

边界条件：

for (int i = 2; i <= n; i++) {}

那么就可以根据这些判断出来的条件撸代码了。

public long subsequence (int n, int[] array) {
    long[] dp = new long[n+1]; // dp[i] 表示当前前 i 个最大和 

    // 初始值
    dp[0] = 0;
    dp[1] = array[0];

    for (int i = 2; i <= n; i++) { // 边界条件
        dp[i] = Math.max(dp[i-1], dp[i-2] + array[i-1]); // 当前的最大值在前一个或者前两个和现在的和之间选择
    }

    return dp[n];
}

这样根据动态规划的理念，这个问题也就解决了。

动态规划优化

如果你还记得斐波那契数列优化版本的话，你就会发现这其中似乎有一些类似的地方，比如：计算当前第 i 个值的结果，只需要参考前两位的结果值，跟其他的都没有关系。
按照这个思路，重新理清楚思路，那么代码就来了！

public long subsequence (int n, int[] array) {
    long one = 0, two = array[0], temp = 0;
    for (int i = 2; i <= n; i++) {
        if (two < one + array[i-1]) { // 当前的最大值在前一个或者前两个和现在的和之间选择
            temp = two;
            two = one + array[i-1];
            one = temp;
        } else {
            two = two;
            one = two;
        }
    }
    return two;
}

这个版本的优化主要在于空间复杂度的优化，以往需要一整个数组来记录，而现在只需要两个变量来代替，极大的节省了空间复杂度。