Constrained Subsequence Sum — Solution in Python, Java & C++
Constrained Subsequence Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Constrained Subsequence Sum is a hard coding problem on arrays, dynamic programming and heap, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Heap, Sliding Window, Queue, Monotonic Queue
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the maximum sum of a non-empty subsequence of nums such that for every pair of consecutive chosen elements at indices i < j, the gap satisfies j - i <= k.
Example 1
Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: Take 10, 2, 5 and 20 — every gap is at most 2.
Example 2
Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so take the least negative value.
Example 3
Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: 10, then −5 to bridge the gap, then 20.
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Hints for Constrained Subsequence Sum
Hint 1
dp[i]= the best sum of a valid subsequence ending ati.Hint 2
dp[i] = nums[i] + max(0, max(dp[i-k..i-1]))— the 0 covers starting fresh ati.Hint 3
A sliding-window maximum over
dpis exactly a monotonic deque.
How to solve Constrained Subsequence Sum
Define dp[i] as the best sum of a valid subsequence ending at i. The previous chosen element is within k positions, so dp[i] = nums[i] + max(0, max(dp[i-k..i-1])). Maintaining that windowed maximum with a monotonic deque makes each step amortised O(1).
Approach
- Keep a deque of indices with decreasing
dpvalues. - At each
i, drop front indices that have fallen out of thek-window. - Set
dp[i] = nums[i] + max(0, dp[front]). - Pop back indices whose
dpis no greater thandp[i], then pushi. - Track the running best
dp[i].
Why it works
The max(0, …) term is what allows a subsequence to start at i rather than extend a loss-making prefix — without it an all-negative array would be forced to chain. And the answer is the best dp[i], not dp[n-1]: the subsequence may end anywhere. A heap works too, but needs lazy deletion of stale indices; the deque avoids that entirely.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The subsequence must be non-empty, so an all-negative array answers with its maximum element, not 0.
- The window covers the previous
kindices, excludingiitself. - The answer is the maximum over all
dp[i], not the last one.
Reference solution
Python
from collections import deque
from typing import List
def constrainedSubsetSum(nums: List[int], k: int) -> int:
n = len(nums)
dp = [0] * n
dq = deque()
best = -(10**9)
for i in range(n):
while dq and dq[0] < i - k:
dq.popleft()
carry = dp[dq[0]] if dq and dp[dq[0]] > 0 else 0
dp[i] = nums[i] + carry
best = max(best, dp[i])
while dq and dp[dq[-1]] <= dp[i]:
dq.pop()
dq.append(i)
return bestJava
public static 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++) {
while (!dq.isEmpty() && dq.peekFirst() < i - k) dq.pollFirst();
int carry = !dq.isEmpty() && dp[dq.peekFirst()] > 0 ? dp[dq.peekFirst()] : 0;
dp[i] = nums[i] + carry;
best = Math.max(best, dp[i]);
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
dq.addLast(i);
}
return best;
}C++
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = (int) nums.size();
vector<int> dp(n, 0);
deque<int> dq;
int best = INT_MIN;
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.front() < i - k) dq.pop_front();
int carry = (!dq.empty() && dp[dq.front()] > 0) ? dp[dq.front()] : 0;
dp[i] = nums[i] + carry;
best = max(best, dp[i]);
while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
dq.push_back(i);
}
return best;
}JavaScript
var constrainedSubsetSum = function(nums, k) {
var n = nums.length;
var dp = [];
for (var t = 0; t < n; t++) dp.push(0);
var deque = [], head = 0;
var best = -2000000000;
for (var i = 0; i < n; i++) {
while (head < deque.length && deque[head] < i - k) head++;
var carry = head < deque.length && dp[deque[head]] > 0 ? dp[deque[head]] : 0;
dp[i] = nums[i] + carry;
if (dp[i] > best) best = dp[i];
while (deque.length > head && dp[deque[deque.length - 1]] <= dp[i]) deque.pop();
deque.push(i);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming