题目描述
给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ,它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。
数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。
样例1
输入:nums = [10,2,-10,5,20], k = 2
输出:37
解释:子序列为 [10, 2, 5, 20] 。
样例2
输入:nums = [-1,-2,-3], k = 1
输出:-1
解释:子序列必须是非空的,所以我们选择最大的数字。
样例3
输入:nums = [10,-2,-10,-5,20], k = 2
输出:23
解释:子序列为 [10, -2, -5, 20] 。
算法1
(动态规划+单调队列优化) $O(n)$
-
$f[i]$表示以$nums[i]$结尾的子序列和的最大值
- 状态转移方程:$f[i] = nums[i] + f[j]$,其中$j$的范围是$i-k$到$i-1$
- 每一次求$f[j]$的代价是扫描一遍这个区间,时间复杂度为$O(nk)$
- 求区间内的最大值,可以用单调队列优化,做到$O(n)$的时间复杂度
Java 代码
class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] f = new int[n];
LinkedList<Integer> q = new LinkedList<>();
int res = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
f[i] = nums[i];
if(q.size() > 0 && q.peekFirst() < i-k) q.pollFirst();
if(q.size() > 0) f[i] = Math.max(f[i], f[q.peekFirst()] + nums[i]);
while(q.size() > 0 && f[q.peekLast()] <= f[i]) q.pollLast();
q.offerLast(i);
res = Math.max(res, f[i]);
}
return res;
}
}