1425. Constrained Subsequence Sum - Explanation

1. Dynamic Programming (Top-Down)

Intuition

We want to find the maximum sum of a subsequence where consecutive elements are at most k indices apart. For each index, we can either start a new subsequence there or extend a previous subsequence. Using recursion with memoization, we explore starting from each position and try extending to any position within the next k indices, taking the maximum result.

Algorithm

Create a memoization array to store computed results for each starting index.
Define a recursive function dfs(i) that returns the maximum subsequence sum starting from index i.
For each index i, initialize the result as nums[i] (taking just this element).
Try extending to each index j in the range [i+1, i+k] and update the result as max(result, nums[i] + dfs(j)).
Store and return the memoized result.
The answer is the maximum of dfs(i) for all starting indices.

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        memo = [None] * len(nums)

        def dfs(i):
            if memo[i] != None:
                return memo[i]

            res = nums[i]
            for j in range(i + 1, len(nums)):
                if j - i > k:
                    break
                res = max(res, nums[i] + dfs(j))

            memo[i] = res
            return res

        ans = float('-inf')
        for i in range(len(nums)):
            ans = max(ans, dfs(i))
        return ans

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(n)$

2. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion, we can solve this iteratively. We define dp[i] as the maximum sum of a constrained subsequence ending at index i. For each position, we look back at the previous k elements and take the best one to extend from (if it improves our sum).

Algorithm

Initialize a DP array where dp[i] = nums[i] (each element starts as its own subsequence).
For each index i from 1 to n-1, iterate through all indices j in the range [max(0, i-k), i-1].
Update dp[i] = max(dp[i], nums[i] + dp[j]) to potentially extend from a previous subsequence.
Return the maximum value in the DP array.

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = [num for num in nums]

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

        return max(dp)

Time & Space Complexity

Time complexity: $O(n * k)$
Space complexity: $O(n)$

3. Dynamic Programming + Segment Tree

Intuition

The bottleneck in the previous approach is finding the maximum DP value in a sliding window of size k. A segment tree can answer range maximum queries in O(log n) time, allowing us to efficiently find the best previous subsequence to extend from.

Algorithm

Build a segment tree that supports point updates and range maximum queries.
Initialize the tree with the first element's value.
For each index i from 1 to n-1:
- Query the segment tree for the maximum value in the range [max(0, i-k), i-1].
- Compute current = nums[i] + max(0, queryResult) (we add 0 if all previous values are negative, meaning we start fresh).
- Update the segment tree at index i with current.
- Track the overall maximum result.
Return the maximum result found.

class SegmentTree:
    def __init__(self, N):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.tree = [float('-inf')] * (2 * self.n)

    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i >>= 1
            self.tree[i] = max(self.tree[i << 1], self.tree[i << 1 | 1])

    def query(self, l, r):
        res = float('-inf')
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return max(0, res)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        maxSegTree = SegmentTree(n)
        maxSegTree.update(0, nums[0])
        res = nums[0]

        for i in range(1, n):
            cur = nums[i] + maxSegTree.query(max(0, i - k), i - 1)
            maxSegTree.update(i, cur)
            res = max(res, cur)

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Max-Heap

Intuition

We can use a max-heap to efficiently track the maximum DP value among the previous k elements. The heap stores pairs of (dp value, index). Before using the top of the heap, we remove any entries that are outside our window (more than k positions behind).

Algorithm

Initialize the result with nums[0] and push (nums[0], 0) onto a max-heap.
For each index i from 1 to n-1:
- Pop elements from the heap while the top element's index is more than k positions behind i.
- Compute current = max(nums[i], nums[i] + heap.top()) to either start fresh or extend.
- Update the result with current.
- Push (current, i) onto the heap.
Return the maximum result.

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        res = nums[0]
        max_heap = [(-nums[0], 0)]  # max_sum, index

        for i in range(1, len(nums)):
            while i - max_heap[0][1] > k:
                heapq.heappop(max_heap)

            cur_max = max(nums[i], nums[i] - max_heap[0][0])
            res = max(res, cur_max)
            heapq.heappush(max_heap, (-cur_max, i))

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

5. Monotonic Deque

Intuition

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).

Algorithm

Initialize a deque with (0, nums[0]) representing (index, dp value) and set result to nums[0].
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.
Return the maximum result.

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

Time & Space Complexity

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

Common Pitfalls

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.

# Wrong: always extends from previous
cur = nums[i] + dq[0][1]

# Correct: start fresh if previous max is negative
cur = nums[i] + max(0, dq[0][1])

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.

# Wrong: just appends without cleanup
dq.append((i, cur))

# Correct: remove smaller values first
while dq and cur > dq[-1][1]:
    dq.pop()
dq.append((i, cur))

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].