Constrained Subsequence Sum

How it works

A monotonic decreasing deque provides O(1) access to the maximum value in a sliding window. We maintain a deque where values are in decreasing order. The front always holds the maximum DP value within our window, and we remove elements from the back that are smaller than the current value (since they will never be useful).

Steps

1. Initialize a deque with (0, nums[0]) representing (index, dp value) and set result to nums[0].
2. For each index i from 1 to n-1:
   • Remove the front element if its index is outside the window (less than i - k).
   • Compute current = max(0, deque.front().value) + nums[i].
   • Remove elements from the back while they have values less than or equal to current.
   • Add (i, current) to the back of the deque.
   • Update the result with current.
3. Return the maximum result.

Complexity

• Time complexity: O(n)
• Space complexity: O(k)

Things to watch for

Forcing Extension When Starting Fresh is Better

When all previous DP values in the window are negative, it's better to start a new subsequence at the current index rather than extending. Failing to take max(0, previous_max) leads to suboptimal sums.

Not Maintaining Monotonic Decreasing Order in Deque

The deque must store values in decreasing order so the front always has the maximum. Forgetting to pop smaller values from the back before inserting breaks this invariant.

Incorrect Window Boundary Check

The constraint allows elements at most k indices apart, meaning index i can extend from indices i-k through i-1. Using < i - k instead of <= i - k - 1 (or equivalently < i - k) for removal is an off-by-one error.

Using O(nk) Approach for Large Inputs

The naive DP solution that checks all k previous elements for each position times out on large inputs. Using a segment tree, heap, or monotonic deque is necessary to achieve O(n log n) or O(n) time.

Returning Maximum DP Value Instead of Tracking Running Maximum

In some implementations, the maximum sum subsequence might not end at the last index. You must track the maximum across all DP values, not just return dp[n-1].

from typing import List
from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dq = deque([(0, nums[0])])
        res = nums[0]

        for i in range(1, n):
            if dq and dq[0][0] < i - k:
                dq.popleft()

            cur = max(0, dq[0][1]) + nums[i]
            while dq and cur > dq[-1][1]:
                dq.pop()

            dq.append((i, cur))
            res = max(res, cur)

        return res

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        deque<pair<int, int>> dq{{0, nums[0]}};
        int res = nums[0];

        for (int i = 1; i < n; i++) {
            if (!dq.empty() && dq.front().first < i - k) {
                dq.pop_front();
            }

            int cur = max(0, dq.front().second) + nums[i];
            while (!dq.empty() && cur > dq.back().second) {
                dq.pop_back();
            }

            dq.emplace_back(i, cur);
            res = max(res, cur);
        }

        return res;
    }
};