Constrained Subsequence Sum: DP with Monotonic Deque

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied. This is LeetCode 1425: Constrained Subsequence Sum.

The constraint means you cannot skip more than k - 1 elements between any two consecutive picks. You are choosing a subsequence where adjacent chosen elements are at most k positions apart. Your goal is to maximize the total sum.

Why this problem matters

This problem sits at the intersection of two powerful techniques: dynamic programming and the monotonic deque. On its own, the DP recurrence is clean and natural. The challenge is computing it efficiently. A naive approach checks up to k previous values at each step, giving O(nk) time. The monotonic deque brings that down to O(n) by maintaining a sliding window maximum over the DP array.

If you have seen Sliding Window Maximum, you already know the deque trick. This problem teaches you how to plug that trick directly into a DP transition. That combination shows up in many hard DP problems, so getting comfortable with it here pays off repeatedly.

The key insight

Define dp[i] as the maximum sum of a valid subsequence that ends at index i. The recurrence is:

dp[i] = nums[i] + max(0, max(dp[j] for j in range(max(0, i-k), i)))

In words: the best subsequence ending at i is the value nums[i] itself, optionally extended by the best subsequence ending within the previous k positions. If all previous dp values are negative, you are better off starting fresh from nums[i] alone, which is why we take max(0, ...).

The problem is that scanning the previous k entries at every step makes this O(nk). But notice what you actually need: the maximum dp value in a sliding window of size k. That is exactly what a monotonic deque does in amortized O(1) per element.

The deque stores indices in decreasing order of their dp values. At each step:

1. Pop indices from the front that have fallen outside the window (index < i - k).
2. The front of the deque is the index with the maximum dp value in the window.
3. Compute dp[i].
4. Pop indices from the back whose dp values are smaller than or equal to dp[i] (they will never be useful again).
5. Push i onto the back.

The solution

from collections import deque

def constrained_subset_sum(nums: list[int], k: int) -> int:
    dp = list(nums)
    dq = deque()

    for i in range(len(nums)):
        # Remove indices outside the window
        if dq and dq[0] < i - k:
            dq.popleft()

        # Extend from the best previous subsequence if beneficial
        if dq:
            dp[i] = max(dp[i], dp[dq[0]] + nums[i])

        # Maintain decreasing order in the deque
        while dq and dp[i] >= dp[dq[-1]]:
            dq.pop()

        dq.append(i)

    return max(dp)

Here is what each piece does:

• dp = list(nums): Initialize dp[i] = nums[i] for every index. This handles the base case where each element starts its own subsequence.
• dq[0] < i - k: If the front index is too far back, it cannot contribute to dp[i], so remove it. Since indices only increase, you never need to remove more than one from the front per step.
• dp[dq[0]] + nums[i]: The front of the deque holds the index with the largest dp value in the window. If extending from that value improves dp[i], take it.
• while dq and dp[i] >= dp[dq[-1]]: Any index at the back with a smaller or equal dp value will never be the window maximum while i is still in range. Discard them.
• dq.append(i): Add the current index to the deque.
• max(dp): The answer could end at any index, so return the overall maximum.

Visual walkthrough

Walk through the example nums = [10, 2, -10, 5, 20] with k = 2. At each step, the deque holds indices whose dp values are in strictly decreasing order. When you process index i, the deque front gives you the best dp value you can extend from. After computing dp[i], you clean up the back of the deque to maintain the decreasing invariant.

Notice how the deque never has more than k + 1 elements, and often has far fewer. The amortized cost is O(1) per element because each index is pushed and popped at most once.

Complexity analysis

Time: Each index is pushed onto and popped from the deque at most once, so the deque operations across all iterations total O(n). The loop itself runs n times. Total: O(n).

Space: The dp array takes O(n). The deque holds at most k indices at any time, but since k can be up to n, the worst case is O(n). Total: O(n).

You could also solve this with a max-heap (priority queue) in O(n log n) time by storing (dp[j], j) pairs and lazily removing stale entries. The deque approach is strictly better in theory and practice.

The building blocks

1. Sliding window maximum with monotonic deque

The core technique here is maintaining the maximum value in a sliding window as it moves across an array. A monotonic deque keeps candidates in decreasing order. When a new element arrives, you pop smaller elements from the back (they are dominated) and remove elements from the front that have left the window. The front always holds the current maximum.

This is exactly LeetCode 239: Sliding Window Maximum. If you are not comfortable with that problem, solve it first. The deque logic in Constrained Subsequence Sum is the same, just applied to dp values instead of raw array values.

2. DP recurrence with constrained lookback

The DP setup follows a common pattern: dp[i] depends on the best value in a window of previous dp entries. Without the constraint, this would be Kadane's algorithm (Maximum Subarray), where dp[i] = max(nums[i], dp[i-1] + nums[i]). The constraint j - i <= k turns the single lookback into a window of size k, which is where the deque comes in.

You will see this same "DP + sliding window optimization" pattern in problems like Jump Game VI (LeetCode 1696) and other hard DP problems where the transition examines a range of previous states.

Edge cases

• All negative values: The problem requires a non-empty subsequence, so you must pick at least one element. The answer is the largest (least negative) element. The algorithm handles this because dp[i] starts as nums[i] and only extends if the deque front provides a positive contribution.
• Single element: Return nums[0]. The loop runs once, and max(dp) returns it.
• k equals the array length: Every previous index is within the window, so the constraint is effectively removed. The deque still works correctly, it just never pops from the front due to window expiration.
• k = 1: Only the immediately preceding element can contribute. This reduces to a variant of Kadane's algorithm where dp[i] = max(nums[i], dp[i-1] + nums[i]).
• Large positive followed by large negatives: The max(0, ...) behavior (implicit in the comparison dp[i] = max(dp[i], dp[dq[0]] + nums[i])) ensures you do not extend a subsequence when doing so would decrease the sum below what nums[i] alone provides.

From understanding to recall

You have walked through the DP recurrence, seen how the monotonic deque optimizes the window maximum lookup, and traced the algorithm step by step. The logic probably feels clear right now. But when you sit down to code this next week, will you remember the deque invariant? Will you get the front-pop condition right on the first try?

Understanding and recall are different skills. Spaced repetition bridges the gap. You revisit the DP + deque pattern at increasing intervals, implement it from scratch each time, and after a few reps the monotonic deque maintenance becomes automatic. No more second-guessing whether you pop from the front or the back first, or whether the comparison is strict or non-strict.

The "DP with sliding window optimization" pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Sliding Window Maximum - The foundational monotonic deque problem
• Maximum Subarray - Kadane's algorithm, the unconstrained version
• House Robber - Another DP problem with adjacency constraints