AlgoMaster Logo

Constrained Subsequence Sum

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This problem asks us to pick a non-empty subsequence from the array where consecutive elements in the subsequence are at most k positions apart. We want to maximize the sum of this subsequence.

This is not a contiguous subarray problem. We can skip elements, but we can't skip too many. If we pick nums[i], the next element we pick must be at some index j where j - i <= k. So we have a "maximum gap" constraint between consecutive picks.

This structure fits dynamic programming. If dp[i] represents the maximum sum of a valid subsequence ending at index i, then dp[i] depends on the best dp[j] values for all j in the range [i-k, i-1]. The element nums[i] must always be included (since the subsequence ends at i), so dp[i] = nums[i] + max(0, max(dp[j]) for j in [i-k, i-1]). We take max(0, ...) because we might be better off starting a new subsequence at i rather than extending a negative-sum one.

The challenge is computing that "max over a sliding window of dp values" efficiently.

Key Constraints:

  • 1 <= nums.length <= 10^5: with n up to 100,000, we need O(n log n) or O(n). An O(n*k) approach degrades to O(n^2) when k is close to n, which is too slow.
  • -10^4 <= nums[i] <= 10^4: values can be negative, and we can't skip all of them. A negative element may be the only stepping stone within range to a large positive value further ahead. The maximum possible sum is 10^5 * 10^4 = 10^9, which fits in a 32-bit signed integer, so no wider type is needed.
  • 1 <= k <= nums.length: k can be as large as n, in which case there is no gap constraint at all.

Approach 1: Dynamic Programming (Brute Force)

Intuition

For every index i, look back at all indices in the range [i-k, i-1] and pick the one with the highest dp value. If that best value is positive, extend that subsequence. If it's negative, start fresh at i.

This computes the recurrence directly: dp[i] = nums[i] + max(0, max(dp[j]) for j in [max(0, i-k), i-1]).

Algorithm

  1. Create a dp array of size n, where dp[i] will store the maximum subsequence sum ending at index i.
  2. Set dp[0] = nums[0].
  3. For each index i from 1 to n-1:
    • Look back at all dp[j] where j is in [max(0, i-k), i-1].
    • Find the maximum among these values.
    • Set dp[i] = nums[i] + max(0, bestPrev).
  4. Return the maximum value in the dp array.

Example Walkthrough

Input:

0
10
1
2
2
-10
3
5
4
20
nums

The dp array fills in left to right. For each index, scan up to k = 2 previous dp values, take the best, and add nums[i]:

1Initialize: dp[0] = nums[0] = 10
0
10
dp[0]=10
1
0
2
0
3
0
4
0
1/6

The answer is max(dp) = 37, produced by the subsequence [10, 2, 5, 20] (indices 0, 1, 3, 4; the gaps between consecutive picks are 1, 2, and 1, all within k = 2).

Code

Each iteration rescans up to k previous dp values, even though the window has shifted by only one position since the last scan. A data structure that maintains the window maximum as elements enter and leave removes that repeated work.

Approach 2: DP with Heap (Priority Queue)

Intuition

Instead of scanning the entire window each time, we can keep the window's dp values in a max-heap (priority queue). The heap gives us the maximum value in O(1) via a peek, and we insert new values in O(log n).

The complication is staleness: the heap's maximum might have fallen out of the window (its index could be more than k positions behind the current index). So each heap entry stores both the dp value and its index, and stale entries are removed lazily.

Algorithm

  1. Create a max-heap. Push (dp[0], 0) into it, where dp[0] = nums[0].
  2. For each index i from 1 to n-1:
    • While the top of the heap has an index less than i - k, pop it (it's outside the window).
    • The heap's top now gives the best dp value in the window.
    • Set dp[i] = nums[i] + max(0, heap_top_value).
    • Push (dp[i], i) into the heap.
    • Update the global result.
  3. Return the maximum dp value.

Example Walkthrough

The trace uses the same input, nums = [10, 2, -10, 5, 20] with k = 2. Each step checks the index of the heap's top entry against the window boundary i - k before reading its value:

1Initialize: dp[0] = nums[0] = 10, push (10, 0) to heap
0
10
dp[0]=10
1
0
2
0
3
0
4
0
1/6

At i = 4 the entry (12, 1) is outside the window, but it never needs to be popped: the larger entry (17, 3) sits above it, so it never reaches the top. This is lazy deletion working as intended.

Code

The heap orders every element in the window, but only the maximum is ever read. The final approach stores only the elements that could still become the maximum and discards everything else, which drops the log factor.

Approach 3: DP with Monotonic Deque (Optimal)

Intuition

This is the "sliding window maximum" technique applied to the dp array. Instead of keeping every dp value in a heap, we maintain a deque of indices whose dp values decrease from front to back. The front of the deque then always holds the maximum dp value in the current window.

A decreasing deque is safe because of a dominance argument. If dp[j] >= dp[i] and j > i (j is newer), then dp[i] will never be the answer for any future query: it expires from the window sooner than j and its value is no larger. So before inserting a new index at the back, we discard every index whose dp value is less than or equal to the new one. No potential window maximum is ever lost, and the deque stays decreasing without any sorting.

Algorithm

  1. Create a deque that stores indices. Initialize it with index 0, and set dp[0] = nums[0].
  2. For each index i from 1 to n-1:
    • Remove indices from the front of the deque that are outside the window (index < i - k).
    • The front of the deque gives the index of the maximum dp value in the window.
    • Set dp[i] = nums[i] + max(0, dp[deque.front()]).
    • Before pushing i onto the back of the deque, remove all indices from the back whose dp values are less than or equal to dp[i].
    • Push i onto the back.
    • Update the global result.
  3. Return the maximum dp value.

Example Walkthrough

Same input once more: nums = [10, 2, -10, 5, 20], k = 2. The deque stores indices. Each step shows which indices get removed from the back so that dp values stay decreasing from front to back:

1Initialize: dp[0] = nums[0] = 10, deque = [0]
0
10
dp[0]=10
1
0
2
0
3
0
4
0
1/6

Over the whole run the deque held at most two indices at a time, while the heap in Approach 2 accumulated every entry it was ever given. Discarding dominated indices on insertion is what removes the log factor.

Code