Sliding Window — Constrained Subsequence Sum
↗ LeetCode: Constrained Subsequence Sum · Hard · pattern chapter →
Max sum of a subsequence where every two consecutive chosen indices differ by at most k.
Example 1 — nums=[10,2,-10,5,20], k=2 → 37Example 2 — nums=[-1,-2,-3], k=1 → -1Example 3 — nums=[10,-2,-10,-5,20], k=2 → 23
Constraints — 1 ≤ n ≤ 10⁵; 1 ≤ k ≤ n. Naive DP is O(nk) — at n=k=10⁵ that's 10¹⁰ ops (~5 minutes). Deque trick is O(n).
Interview timer00:00
Approach 1 — Brute DP with inner window scan
Intuition. dp[i] = nums[i] + max(0, max(dp[i-k..i-1])). For each i, scan back k positions.
int constrainedSubsetSumBrute(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
int best = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int maxPrev = 0;
for (int j = Math.max(0, i - k); j < i; j++)
maxPrev = Math.max(maxPrev, dp[j]);
dp[i] = nums[i] + maxPrev;
best = Math.max(best, dp[i]);
}
return best;
}Complexity — Time O(nk); Space O(n). For n=k=10⁵: 10¹⁰ ops = TLE. In an interview state this then reach for a monotonic deque.
Approach 2 — DP with monotonic deque (canonical)
Insight. The inner scan is a sliding-window max. Replace it with a monotonic deque of indices with decreasing dp values — the front is always the current window max in O(1) amortised.
int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
Deque<Integer> dq = new ArrayDeque<>();
int best = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
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);
if (dq.peekFirst() == i - k) dq.pollFirst();
best = Math.max(best, dp[i]);
}
return best;
}Complexity — Time O(n); Space O(k). Say aloud in an interview: "same monotonic-deque pattern as Sliding Window Maximum and Jump Game VI — reusable across every 'DP with window max/min' problem."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute DP (window scan) | O(nk) | O(n) | Reference; TLE at 10⁵ |
| DP + monotonic deque | O(n) | O(k) | Canonical |
When to use which
- "Max/min over sliding window of DP values" → monotonic deque.
- Jump-game family → same template.
- k = 1 → same skeleton, deque may be size 1.