牛客题解-NC144不相邻最大子序列和

题目

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

注意:

  1. 三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)

  2. 解集中不能包含重复的三元组。

    1
    例如,给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)

示例1

输入:

1
3,[1,2,3]

返回值:

1
4

说明:

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

示例2

输入:

1
4,[4,2,3,5]

输出:

1
9

说明:

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

思路

分析

该问题为动态规划问题。

用一个长度为n+1的数组dp[n+1]来保存各个位置的最佳解。

首先初始化dp[0] = 0; dp[1] = array[0];

后续具体的状态转移过程可以描述为:

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

最终得到的dp[n]则为所求解。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
long[] dp = new long[n+1];
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];
}
}