lc.1425.带限制的子序列和
给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。
数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
示例 1：
1
2
3
|
输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。
|
示例 2：
1
2
3
|
输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。
|
示例 3：
1
2
3
|
输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。
|
提示：
$1 <= k <= nums.length <= 10^5$
$-10^4 <= nums[i] <= 10^4$
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
//dp[i] = max(dp[j],0) + nums[j] (i-j<=k) and j<i
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = nums.size();
if (n<=0) return 0;
vector<int> dp(n+1);
deque<int> q;
q.push_back(0);
dp[0] = nums[0];
int res = nums[0];
for (int i=1;i<n;i++) {
while(q.size() && q.front() < i- k) q.pop_front();
// 单调栈顶部就是最大d，直接取出计算即可
// 坑：排除负数，此时宁愿只取nums[i]
dp[i] = max(0,dp[q.front()]) + nums[i];
res = max(res,dp[i]);
/// 构建单调栈, 弹出队列里比自己小
while(q.size() && dp[i] > dp[q.back()]) q.pop_back();
q.push_back(i);
}
return res;
}
};
|
