LeetCode 1425: Constrained Subsequence Sum (DP + Monotonic Deque)
LeetCode 1425DPMonotonic DequeToday we solve LeetCode 1425 - Constrained Subsequence Sum.
Source: https://leetcode.com/problems/constrained-subsequence-sum/
English
Problem Summary
Given an integer array nums and an integer k, choose a non-empty subsequence such that adjacent chosen indices differ by at most k. Return the maximum possible sum.
Key Insight
Let dp[i] be the best sum of a valid subsequence ending at index i. Then dp[i] = nums[i] + max(0, max(dp[j])) where i-k ≤ j < i. We need a sliding-window maximum over dp.
Why Monotonic Deque
A deque can maintain candidate indices in decreasing dp order. The front is always the largest dp in the last k positions, so each index is pushed and popped at most once.
Algorithm
Scan from left to right, first removing out-of-window indices. Use deque front as the window max for transition. After computing dp[i], pop smaller values from the back, then push i. Track global maximum.
Complexity
Time: O(n), Space: O(n) for dp and deque.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
Deque<Integer> dq = new ArrayDeque<>();
int ans = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
dp[i] = nums[i] + (dq.isEmpty() ? 0 : Math.max(0, dp[dq.peekFirst()]));
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
dq.offerLast(i);
ans = Math.max(ans, dp[i]);
}
return ans;
}
}func constrainedSubsetSum(nums []int, k int) int {
n := len(nums)
dp := make([]int, n)
dq := []int{}
ans := nums[0]
for i := 0; i < n; i++ {
for len(dq) > 0 && dq[0] < i-k {
dq = dq[1:]
}
best := 0
if len(dq) > 0 && dp[dq[0]] > 0 {
best = dp[dq[0]]
}
dp[i] = nums[i] + best
for len(dq) > 0 && dp[dq[len(dq)-1]] <= dp[i] {
dq = dq[:len(dq)-1]
}
dq = append(dq, i)
if dp[i] > ans {
ans = dp[i]
}
}
return ans
}class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n);
deque<int> dq;
int ans = INT_MIN;
for (int i = 0; i < n; ++i) {
while (!dq.empty() && dq.front() < i - k) dq.pop_front();
dp[i] = nums[i] + (dq.empty() ? 0 : max(0, dp[dq.front()]));
while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
dq.push_back(i);
ans = max(ans, dp[i]);
}
return ans;
}
};from collections import deque
class Solution:
def constrainedSubsetSum(self, nums, k):
n = len(nums)
dp = [0] * n
dq = deque()
ans = -10**18
for i in range(n):
while dq and dq[0] < i - k:
dq.popleft()
dp[i] = nums[i] + (max(0, dp[dq[0]]) if dq else 0)
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
ans = max(ans, dp[i])
return ansfunction constrainedSubsetSum(nums, k) {
const n = nums.length;
const dp = new Array(n).fill(0);
const dq = [];
let ans = -Infinity;
for (let i = 0; i < n; i++) {
while (dq.length && dq[0] < i - k) dq.shift();
dp[i] = nums[i] + (dq.length ? Math.max(0, dp[dq[0]]) : 0);
while (dq.length && dp[dq[dq.length - 1]] <= dp[i]) dq.pop();
dq.push(i);
ans = Math.max(ans, dp[i]);
}
return ans;
}中文
题目概述
给定整数数组 nums 和整数 k，要求选择一个非空子序列，并且相邻被选下标差值不超过 k。返回可获得的最大子序列和。
核心思路
定义 dp[i] 为“以 i 结尾”的最大合法和，则有 dp[i] = nums[i] + max(0, max(dp[j]))，其中 i-k ≤ j < i。问题变成维护长度为 k 窗口内的 dp 最大值。
为什么用单调队列
双端队列按 dp 值单调递减存候选下标，队首就是窗口最大值。每个下标最多进出一次，总复杂度线性。
算法步骤
从左到右遍历：先弹出过期下标，再用队首完成状态转移。计算完 dp[i] 后，从队尾移除不优候选并入队 i，同时维护全局答案。
复杂度分析
时间复杂度 O(n)，空间复杂度 O(n)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
Deque<Integer> dq = new ArrayDeque<>();
int ans = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
dp[i] = nums[i] + (dq.isEmpty() ? 0 : Math.max(0, dp[dq.peekFirst()]));
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
dq.offerLast(i);
ans = Math.max(ans, dp[i]);
}
return ans;
}
}func constrainedSubsetSum(nums []int, k int) int {
n := len(nums)
dp := make([]int, n)
dq := []int{}
ans := nums[0]
for i := 0; i < n; i++ {
for len(dq) > 0 && dq[0] < i-k {
dq = dq[1:]
}
best := 0
if len(dq) > 0 && dp[dq[0]] > 0 {
best = dp[dq[0]]
}
dp[i] = nums[i] + best
for len(dq) > 0 && dp[dq[len(dq)-1]] <= dp[i] {
dq = dq[:len(dq)-1]
}
dq = append(dq, i)
if dp[i] > ans {
ans = dp[i]
}
}
return ans
}class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n);
deque<int> dq;
int ans = INT_MIN;
for (int i = 0; i < n; ++i) {
while (!dq.empty() && dq.front() < i - k) dq.pop_front();
dp[i] = nums[i] + (dq.empty() ? 0 : max(0, dp[dq.front()]));
while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
dq.push_back(i);
ans = max(ans, dp[i]);
}
return ans;
}
};from collections import deque
class Solution:
def constrainedSubsetSum(self, nums, k):
n = len(nums)
dp = [0] * n
dq = deque()
ans = -10**18
for i in range(n):
while dq and dq[0] < i - k:
dq.popleft()
dp[i] = nums[i] + (max(0, dp[dq[0]]) if dq else 0)
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
ans = max(ans, dp[i])
return ansfunction constrainedSubsetSum(nums, k) {
const n = nums.length;
const dp = new Array(n).fill(0);
const dq = [];
let ans = -Infinity;
for (let i = 0; i < n; i++) {
while (dq.length && dq[0] < i - k) dq.shift();
dp[i] = nums[i] + (dq.length ? Math.max(0, dp[dq[0]]) : 0);
while (dq.length && dp[dq[dq.length - 1]] <= dp[i]) dq.pop();
dq.push(i);
ans = Math.max(ans, dp[i]);
}
return ans;
}
Comments