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

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

方法一：动态规划

求解思路
对于本题目要求在不相邻的位置时求解最大子序列的和。这道题目是一个01背包问题，即根据前边计算好的i个节点的结果判断是否选择当前节点，我们假定dp[i]为i位置最大子序列的和，其状态转移方程为： $图片说明$ ，其中array[i]表示题目所给的数组在第i位置上的数，根据以上描述即可求解出相应的结果。

图片说明

解题代码

import java.util.*;
public class Solution {
    public long subsequence (int n, int[] array)
    {
        if (n == 0)
        {
            return 0;
        }
        long[] hydp = new long[n]; // 创建一维数组，辅助计算
        hydp[0] = Math.max(0,array[0]); // 当序列长度为1时
        if (n == 1)
        {
            return hydp[0];
        }
        // 序列长度为2
        hydp[1] = Math.max(hydp[1],array[1]);
        // 对hydp进行遍历
        for(int i = 2;i < n;++i)
        {
            hydp[i] = Math.max(hydp[i-1],hydp[i-2] + array[i]);
        }
        return hydp[n-1]; // 返回结果
    }
}

复杂度分析
时间复杂度：使用了一层循环，因此时间复杂度为 $O(N)$
空间复杂度：引入dp[n]数组，因此空间复杂度为 $O(N)$

方法二：优化方法--动态优化

求解思路
对于本题目的求解，我们参考斐波那契数列的通项公式，在计算第n个值时，发现其结果可以由前两位的结果得出，跟其他位置的值无联系。因此我们对于第一种方法做出优化。

图片说明

解题代码

import java.util.*;
public class Solution {
    public long subsequence (int n, int[] array) {
    long i=0,j=0,k=0; // 声明ijk三个变量
    for(int x=n-1;x>=0;x--)
    {
        k=Math.max(i,array[x]+j); // k存储最大值
        j=i; // 更新j值
        i=k; // 更新i值
    }
    return k; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：引入one,two两个变量，常数级内存空间，因此空间复杂度为 $O(1)$