Constrained Subsequence Sum — Hard Problem & Solution

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…

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Sliding Window, Heap, 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

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 dp values.
At each i, drop front indices that have fallen out of the k-window.
Set dp[i] = nums[i] + max(0, dp[front]).
Pop back indices whose dp is no greater than dp[i], then push i.
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 k indices, excluding i itself.
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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue