Constrained Subsequence Sum

Hard
1062.

Constrained Subsequence Sum

Constrained Subsequence Sum is a hard coding problem on arrays, dynamic programming and heap, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var constrainedSubsetSum = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    dp[i] = the best sum of a valid subsequence ending at i.

  2. Hint 2

    dp[i] = nums[i] + max(0, max(dp[i-k..i-1])) — the 0 covers starting fresh at i.

  3. Hint 3

    A sliding-window maximum over dp is 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

  1. Keep a deque of indices with decreasing dp values.
  2. At each i, drop front indices that have fallen out of the k-window.
  3. Set dp[i] = nums[i] + max(0, dp[front]).
  4. Pop back indices whose dp is no greater than dp[i], then push i.
  5. 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

Java

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