描述

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

方法一

思路

• 枚举，递归，回溯；
• 所求子序列集合要求各个元素之间互不相邻，假设所给数组为arr，对于下标为index的元素总共两种选择，将其放入子序列集合或者是不放入，那么便存在如下递推公式：
  f(n-1)表示不要当前元素，f(n-2)表示将当前元素纳入最大子序列集合中，n需要大于等于3，
  而当n = 1时，
  当n = 2时，
• 故可以依据上述递推公式，递归计算不相邻最大子序列和。
• 代码如下：

import java.util.*;


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

    public long subsequence (int n, int[] array) {
       return getMax(0,array);
    }
    private long getMax(int start,int[] array){
        if (start >= array.length){
            return 0;
        }
        // 子序列中包含array[start]的最大子序列和
        long taken = 0;
        // 子序列中不包含array[start]的最大子序列和
        long untaken = 0;
        // 不包含
        untaken = getMax(start + 1,array);
        // 若array[start] 小于等于0，则直接不要该数
        if (array[start] <= 0){
            return untaken;
        }
        // 包含
        taken = getMax(start + 2,array) + array[start];
        // 取最大值
        return Math.max(taken,untaken);
    }
}

• 时间复杂度：，递归函数的计算时间复杂度为指数级；
• 空间复杂度：，递归调用栈的空间大小为n。

方法二

思路

• 动态规划；
• 方法一的时间复杂度过大，程序运行期间栈溢出；
• 方法一在递归运算中会有很多的冗余计算，譬如说在计算f(4)时，需要取计算f(3),f(2),f(1)等。
• 故可以在采用自底向上的方法，依据方法一的递推公式，记录每一个子问题的最大子序列和，从而降低时间复杂度。
• 创建一维数组dp存放计算的结果
• 依次计算f(1),f(2),f(3)……f(n)
• f(n)即为所求的不相邻最大子序列和。
• 对于数组[4,3,2,1,5,6,7]参考下图示例：
  
• 代码如下：

import java.util.*;


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

    public long subsequence (int n, int[] array) {
        if (n == 0){
            return 0;
        }
        // 创建一维数组，辅助计算
        long[] dp = new long[n];
        // 当序列长度为1时
        dp[0] = Math.max(0,array[0]);
        if (n == 1){
            return dp[0];
        }
        // 序列长度为2时
        dp[1] = Math.max(dp[1],array[1]);
        // 遍历
        for(int i = 2;i < n;++i){
            dp[i] = Math.max(dp[i-1],dp[i-2] + array[i]);
        }
        return dp[n-1];
    }
}

• 时间复杂度：，一层循环；
• 空间复杂度：，一维数组；

方法三

思路

• 动态规划
• 方法二的空间复杂度为，可以考虑将其降低为；
• 在计算f(n)中实际上用到的也就是f(n-1)和f(n-2)，所以只需设置两个变量b(f(n-1))，a(f(n-2))，在每一轮计算过后更新a=b,b=f(n)即可。
• 代码如下：

import java.util.*;


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

    public long subsequence (int n, int[] array) {
        if (n == 0){
            return 0;
        }
        // 当序列长度为1时
        long a = Math.max(0,array[0]);
        if (n == 1){
            return a;
        }
        // 序列长度为2时
        long b = Math.max(a,array[1]);
        // 遍历
        for(int i = 2;i < n;++i){
            long temp = b;
            b = Math.max(b,a + array[i]);
            a = temp;
        }
        return b;
    }
}

• 时间复杂度：，一重循环；
• 空间复杂度：，常数级空间复杂度。