不相邻最大子序列和

题目描述

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

示例1

输入

复制

3,[1,2,3]

返回值

复制

4

说明

有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4 

示例2

输入

复制

4,[4,2,3,5]

返回值

复制

9

说明

其中[4,5]的选取方案是在满足不同时选取相邻位置的数的情况下是最优的答案 

备注:

输入的值在int范围内

题目意思

类似于小偷问题，不能偷相邻位置的元素

一维动态规划

学习类似于数学归纳法的思想考虑初始条件：

• 当数组中只有一个元素时，最大收益是偷这一个

• 当数组中有两个元素时，最大收益是偷两个中的最大值

• 当数组中有大于两个元素时，最大收益是dp[i] = Math.max(dp[i-1],dp[i-2]+array[i])

import java.util.*;
public class Solution {
    public long subsequence (int n, int[] array) {
        long []dp = new long[n];
        if(n==0)return 0;
        if(n==1)return array[0];
        dp[0] = array[0];
        dp[1] = Math.max(array[0],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];
    }

二维动态规划

import java.util.*;
public class Solution {
    public long subsequence (int n, int[] array) {
        long [][]dp = new long[n][2];
        if(n==1){
            return array[0];
        }else if(n==2){
            return Math.max(array[0],array[1]);
        }
        dp[0][0] = 0;
        dp[0][1] = array[0];
        
        for(int i=1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][1],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+array[i]);
        }
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
}

赏

谢谢你请我吃糖果

微信