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

描述
给你一个n（1≤n≤10^5），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。
示例

输入：3,[1,2,3]
返回值：4
说明：有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4

这道题本质上是“打家劫舍”问题，可以用动态规划解决，我们换个说法解释这道题：“当一个盗贼打算偷抢房屋的钱财时，两间相邻的房屋在同一个晚上被抢时，系统会自动报警，在不触碰到报警设备时，求他能抢到的最高金额。”
解决动态规划问题首先要找到状态和选择，这里的状态就是你面前房子的索引，
选择有两个：
1.不抢这间房子，到下一间做选择
2.抢这间房子，那么下一间就不能抢，只能走到下下一间做选择

图片说明
方法一：自顶向下(递归)

从上面这张递归的图片上看， $dp(0)$ 需要计算 $dp(1)$ 和 $dp(2)$ ，而 $dp(1)$ 会重复计算 $dp(2)$ ,为了避免重复计算，减小复杂度，我们可以定义一个记忆数组，将其初始化为全部是-1，每计算出一次结果，将其记录到 $memory$ 数组中，如果 $memory[start]$ 的值不是-1,说明 $dp[start]$ 已经被计算过，则直接返回结果，否则继续进入下一层递归计算

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型vector 长度为n的数组
     * @return long长整型
     */

    long long subsequence(int n, vector<int>& array) {
        // write code here
        vector<long long>memory(n);
        //初始化memory数组为-1
        for(int i=0;i<n;i++){
            memory[i]=-1;
        }
        return dp(array,0,memory);
    }
    long long dp(vector<int>&array,int start,vector<long long>&memory){
        //递归终止条件
        if(start>=array.size())return(long)0;
        //避免重复计算
        if(memory[start]!=-1)return memory[start];
        //不抢这间房子到下一间房子做选择与抢这间房子，到下下一间房子做选择之间择优
        long long res= max(dp(array,start+1,memory),(long long)array[start]+dp(array,start+2,memory));
        //对已经计算过的进行标记
        memory[start]=res;
        return res;
    }
};

复杂度：

时间复杂度： $O(n)$ ,初始化记忆数组的时间复杂度为 $O(n)$ ,递归的时间复杂度在于每次递归的时间复杂度和递归深度，每次递归的操作复杂度为常数级 $O(1)$ ,递归深度为 $n$ ，因此时间复杂度为 $O(n)$
空间复杂度：记忆数组的大小为 $n$ ，递归深度为 $n$ ，因此空间复杂度为 $O(n)$

方法二：自底向上
递归算法的复杂度过高，当数组太大时递归深度过深会导致运行超时，因此我们可以考虑用dp数组来记录状态，要求得 $dp[i]$ ，我们需要从后往前递推 $dp$ 数组,因此我们从后往前遍历 $dp$ 数组
图片说明
代码如下：

import java.util.*;
public class Solution {
    /**
 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 计算
 @param n int整型 数组的长度
 @param array int整型一维数组 长度为n的数组
 @return long长整型
      */
     public long subsequence (int n, int[] array) {
         // write code here
         //dp[i]代表从第i间房子开始抢，能抢劫到的最多的钱
         long[]dp=new long[n+2];
         for(int i=n-1;i>=0;i--){
             dp[i]=Math.max(dp[i+1],array[i]+dp[i+2]);
         }
         return dp[0];
     }
 }

复杂度：
时间复杂度：需要遍历一遍数组，数组长度为 $n$ ,则时间复杂度为 $O(n)$
空间复杂度：额外辅助空间 $dp$ 数组的大小为 $n$ ,空间复杂度为 $O(n)$

方法三：状态压缩后的动态规划
我们发现，状态转移方程只与 $dp[i+1]$ 和dp $[i+2]$ 有关，因此为了提升空间效率，可以采用迭代的方法更新 $dp_i,dp_i1,dp_i2$

import java.util.*;
public class Solution {
    /**
 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 计算
 @param n int整型 数组的长度
 @param array int整型一维数组 长度为n的数组
 @return long长整型
      */
     public long subsequence (int n, int[] array) {
         // write code here
         //分别记录dp[i+1],dp[i+2]
         int dp_i=0,dp_i1=0,dp_i2=0 ;
         for(int i=n-1;i>=0;i--){
             dp_i=Math.max(dp_i1,array[i]+dp_i2);
             dp_i2=dp_i1;
             dp_i1=dp_i;
       }
         return dp_i;
     }
 }

复杂度：

时间复杂度：需要遍历一遍数组，数组长度为 $n$ ,则时间复杂度为 $O(n)$
空间复杂度：额外辅助空间为常数级，空间复杂度为 $O(1)$