LeetCode · #1425

Constrained Subsequence Sum Solution

Combine dynamic programming with a monotonic deque so each state can grab the best value from the last k positions in O(1).

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #1425

🏗️

Pattern

DP + Monotonic Deque

Pick a non-empty subsequence such that for every pair of consecutive chosen elements, their indices differ by at most k. Return the maximum possible sum.

Example

 Input: nums = [10, 2, -10, 5, 20], k = 2 Output: 37 // Choose 10, 2, 5, 20 

Section Two · Brute Force

Naive DP — O(n · k)

Let dp[i] be the best subsequence sum ending at index i. Then look back over the previous k positions to find the best predecessor.

Problem: Scanning the last k states for every i costs O(n·k). When both are large, that times out.

Section Three · Optimal

DP + Monotonic Deque — O(n)

The recurrence is:

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

So for each index, we only need the maximum dp value from the previous k indices. A decreasing deque gives that in O(1).

💡 Mental model: Imagine every index wants advice from the strongest candidate in the last k seats. The deque keeps those candidates sorted by strength, so the best one is always at the front.

Algorithm

Remove indices from the front if they are more than k positions behind.
Compute dp[i] = nums[i] + max(0, dp[dq.front]) if the deque is non-empty.
Pop smaller or equal dp values from the back, because the new state dominates them.
Push i into the deque and update the global answer.

Why use max(0, ...)?:

A negative previous subsequence would only make the current sum worse.
In that case, start a fresh subsequence at i.

Section Four · Walkthrough

Visual Walkthrough

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

Section Five · Code

Code — Java & Python

Java — DP + deque

 import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
Deque<Integer> dq = new ArrayDeque<>();
int ans = nums[0];
for (int i = 0; i < n; i++) {
while (!dq.isEmpty() && dq.peekFirst() < i - k)
                dq.pollFirst();

            dp[i] = nums[i] + (dq.isEmpty() ? 0 : Math.max(0, dp[dq.peekFirst()]));
            ans = Math.max(ans, dp[i]);
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i])
                dq.pollLast();

            dq.offerLast(i);
        }
return ans;
    }
}

Python — DP + deque

 from collections import deque
class Solution:
def constrainedSubsetSum(self, nums: list[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dq = deque()
        ans = nums[0]
for i, num in enumerate(nums):
while dq and dq[0] < i - k:
                dq.popleft()

            dp[i] = num + (0 if not dq else max(0, dp[dq[0]]))
            ans = max(ans, dp[i])
while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()

            dq.append(i)
return ans

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Naive DP	O(n · k)	O(n)
DP + monotonic deque	O(n)	O(n)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	What happens	Why it matters
All numbers negative	Return the largest single element	The subsequence must be non-empty.
`k = 1`	Only adjacent chaining allowed	The recurrence still works without changes.
Large positive streak	Deque front keeps the strongest prior sum	This is where the O(n) optimization shines.

⚠ Common Mistake: Forgetting to remove expired indices before reading the deque front. That lets states older than k illegally influence the answer.

← Back to Deque practice

LearningTree

LC 1425 · Constrained Subsequence Sum — Solution & Explanation | DSA Guide