Constrained Subsequence Sum

1. Define the problem

Pick some numbers from the array, keeping their original order, so that any two numbers you pick are at most k positions apart . Return the largest total you can make. You must pick at least one number. Work out, for each index, the best total of a selection that ends exactly there. That is the value at i plus the best of the previous k answers, or plus nothing at all if all of them are negative, because you are free to start fresh at i. A monotonic deque keeps the largest of those previous k answers available at the front without ever scanning them, so the whole array is handled in one pass.

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums_i ≤ 10⁴
At least one number must be picked, so an all negative array gives a negative answer
The answer is the best total over every index, not just the last one

Example

Inputnums = [10, 2, -10, 5, 20], k = 2

Output37

Explanation Pick 10, 2, 5 and 20. Each neighbouring pair is at most 2 positions apart, and they add up to 37.

2. Know the words first

In plain terms

Subsequence: Numbers picked from the array in their original order, with gaps allowed. It is not the same as a contiguous run.
Gap limit k: The most positions allowed between two numbers you pick that are next to each other in your selection. It is why only the previous k answers matter.
Monotonic deque: A double ended queue of indexes kept so their answers only go down from front to back, which makes the front the largest one still in range.
Starting fresh: Choosing to begin a new selection at index i rather than extend an earlier one. That is what taking the larger of the previous answer and 0 means.

3. Visualize the solution

One row of cells is the best total ending at each index; the frame is the k position reach

010

1—

2—

3—

4—

Statusinit

i = 0: nothing comes before it, so best[0] = 10 and the answer so far is 10.

What happens in this step

nums = [10, 2, -10, 5, 20], k = 2
deque is empty, so bestPrev = 0
best[0] = 10 + 0 = 10
answer so far = 10

The deque = [0] after this step.

Step 1 of 8

Steps to visualize

Each cell holds the best total for a selection that ends exactly at that index.
The highlight frame spans the indexes that could come just before i, which is i - k up to i.
Take the front of the deque, but never below zero, because starting fresh is always allowed.
After filling a cell, drop any index at the back whose total is no better, then add the new index.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the best total ending at each index; the frame is the k position reach

010

1—

2—

3—

4—

Statusinit

i = 0: nothing comes before it, so best[0] = 10 and the answer so far is 10.

What happens in this step

nums = [10, 2, -10, 5, 20], k = 2
deque is empty, so bestPrev = 0
best[0] = 10 + 0 = 10
answer so far = 10

The deque = [0] after this step.

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function constrainedSubsetSum(nums, k) {
  const dp = new Array(nums.length).fill(0);
  const window = [];
  let best = nums[0];

  for (let i = 0; i < nums.length; i++) {
    while (window.length > 0 && window[0] < i - k) {
      window.shift();
    }

    const bestPrev = window.length > 0 ? Math.max(dp[window[0]], 0) : 0;
    dp[i] = nums[i] + bestPrev;

    if (dp[i] > best) {
      best = dp[i];
    }

    while (window.length > 0 && dp[window[window.length - 1]] <= dp[i]) {
      window.pop();
    }

    window.push(i);
  }

  return best;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [10, 2, -10, 5, 20], k = 2`	`37`	example from the docstring
`nums = [-1, -2, -3], k = 1`	`-1`	at least one number must be picked, so the least bad single value wins
`nums = [10, -2, -10, -5, 20], k = 2`	`23`	the gap limit forces a negative number into the selection
`nums = [5], k = 1`	`5`	smallest possible input
`nums = [1, 2, 3, 4], k = 4`	`10`	every number is worth taking when all are positive
`nums = [-5, -1, -4], k = 2`	`-1`	a wider gap limit still cannot beat picking one number

Constrained Subsequence Sum