Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Constrained Subsequence Sum

Try it yourself
HardProblemExternal link

Description

Given an integer array nums and an integer k, return the largest sum of a non-empty subsequence of nums in which every two consecutive chosen elements are at most k indexes apart: for chosen indexes i < j with nothing chosen between them, j - i <= k.

A subsequence keeps the array's order and may skip elements; here the skips are limited to fewer than k elements in a row.

Examples

Example 1

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

Output: 37

Explanation: Take 10, 2, 5 and 20: the gaps are 1, 2 and 1, all within 2, for 37.

Example 2

Input: nums = [-1, -2, -3], k = 1

Output: -1

Explanation: The subsequence can't be empty, so the best is the single largest value, −1.

Example 3

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

Output: 23

Explanation: Take 10, −2, −5 and 20, for 23: skipping both −2 and −10 would leave a gap of 3.

Constraints

  • 1 ≤ k ≤ nums.length ≤ 10^5
  • −10^4 ≤ nums[i] ≤ 10^4

Editorial

Brute Force

Intuition

Let dp[i] be the best sum of a valid subsequence that ends on index i. Before i, it either had nothing (it starts at i) or its previous element was one of the k indexes before i. Starting fresh is worth 0, so:

dp[i] = nums[i] + max(0, dp[i - k], …, dp[i - 1])

The subsequence may end anywhere, so the answer is the largest dp[i].

Step-by-Step Explanation

Let's trace nums = [10, 2, -10, 5, 20], k = 2:

  1. Index 0: no earlier answers, so start fresh with 0; dp[0] = 10 + 0 = 10.
  2. Index 1: the answers in reach are 10, best 10; dp[1] = 2 + 10 = 12.
  3. Index 2: the answers in reach are 10 and 12, best 12; dp[2] = −10 + 12 = 2.
  4. Index 3: the answers in reach are 12 and 2, best 12; dp[3] = 5 + 12 = 17.
  5. Index 4: the answers in reach are 2 and 17, best 17; dp[4] = 20 + 17 = 37.

Rescan the Last k Answers — The outlined window holds the indexes that index i can follow.

Algorithm

  1. For each i: best = 0, then best = max(best, dp[j]) for j from max(0, i - k) to i - 1.
  2. dp[i] = nums[i] + best.
  3. Return the largest dp[i].

Code

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);                   // dp[i]: the best sum of a subsequence that ends on i
        int answer = INT_MIN;
        for (int i = 0; i < n; i++) {
            int best = 0;                    // 0: start a new subsequence at i
            for (int j = max(0, i - k); j < i; j++)   // every index i can follow
                best = max(best, dp[j]);
            dp[i] = nums[i] + best;
            answer = max(answer, dp[i]);
        }
        return answer;
    }
};

class Solution:
    def constrainedSubsetSum(self, nums: list[int], k: int) -> int:
        dp = [0] * len(nums)                 # dp[i]: the best sum of a subsequence that ends on i
        for i, x in enumerate(nums):
            best = 0                         # 0: start a new subsequence at i
            for j in range(max(0, i - k), i):   # every index i can follow
                best = max(best, dp[j])
            dp[i] = x + best
        return max(dp)

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];                    // dp[i]: the best sum of a subsequence that ends on i
        int answer = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int best = 0;                         // 0: start a new subsequence at i
            for (int j = Math.max(0, i - k); j < i; j++)   // every index i can follow
                best = Math.max(best, dp[j]);
            dp[i] = nums[i] + best;
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }
}

var constrainedSubsetSum = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n).fill(0);         // dp[i]: the best sum of a subsequence that ends on i
    let answer = -Infinity;
    for (let i = 0; i < n; i++) {
        let best = 0;                        // 0: start a new subsequence at i
        for (let j = Math.max(0, i - k); j < i; j++)   // every index i can follow
            best = Math.max(best, dp[j]);
        dp[i] = nums[i] + best;
        answer = Math.max(answer, dp[i]);
    }
    return answer;
};

Complexity Analysis

Time Complexity: O(n·k)

Each index scans up to k earlier answers.

Space Complexity: O(n)

The dp array.

Why This Approach Is Not Efficient

With 10^5 values and k = 5 × 10^4, that's billions of reads, over the time limit in Python and JavaScript. But the window dp[i - k .. i - 1] slides one step for each i, and all it's asked for is its maximum: a sliding window maximum over the dp values. A heap would give it in O(log n); a monotonic deque gives it in O(1) on average.

Optimal Approach - A Monotonic Deque Over dp

Intuition

Keep a deque of indexes whose dp values fall from front to back. For each i: pop the front if it's more than k back (< i - k); then dp[i] = nums[i] + max(0, dp[front]); then pop the back while its dp is ≤ dp[i], since i is later and at least as good, and push i. Track the largest dp as you go.

It's Jump Game VI's recurrence with two changes: the max(0, …), because a subsequence may start anywhere, and the answer, which is the best dp anywhere rather than the last one.

Step-by-Step Explanation

Let's trace nums = [10, 2, -10, 5, 20], k = 2:

  1. Nothing to follow, so dp[0] = 10.
  2. Follow index 0, so dp[1] is 2 + 10 = 12. It knocks 10 off the back.
  3. Follow index 1, so dp[2] is −10 + 12 = 2.
  4. Follow index 1, so dp[3] is 5 + 12 = 17. It knocks 2 and 12 off the back.
  5. Follow index 3, so dp[4] is 20 + 17 = 37. It knocks 17 off the back.

The Best of the Last k, Kept in Front — The bottom row holds the deque's dp values, falling; its front is the best one to follow.

Algorithm

  1. Start with an empty deque and answer = −∞.
  2. For each i: pop the front if it's < i - k; dp[i] = nums[i] + max(0, dp[front]) (or just nums[i] if the deque is empty); pop the back while dp[back] <= dp[i]; push i; update answer.
  3. Return answer.

Code

JavaScript keeps the deque in an array with a head and a tail index: every index is pushed once, so n slots are enough.

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);                   // dp[i]: the best sum of a subsequence that ends on i
        deque<int> dq;                       // indexes, their dp values falling: the front is the best
        int best = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (!dq.empty() && dq.front() < i - k)
                dq.pop_front();              // more than k back: too far to follow
            dp[i] = nums[i] + max(0, dq.empty() ? 0 : dp[dq.front()]);   // start afresh if it's better
            while (!dq.empty() && dp[dq.back()] <= dp[i])
                dq.pop_back();
            dq.push_back(i);
            best = max(best, dp[i]);
        }
        return best;
    }
};

from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums: list[int], k: int) -> int:
        dp = [0] * len(nums)                 # dp[i]: the best sum of a subsequence that ends on i
        dq = deque()                         # indexes, their dp values falling: dq[0] is the best
        for i, x in enumerate(nums):
            if dq and dq[0] < i - k:
                dq.popleft()                 # more than k back: too far to follow
            dp[i] = x + max(0, dp[dq[0]] if dq else 0)   # start afresh when every earlier sum is negative
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)
        return max(dp)

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];                    // dp[i]: the best sum of a subsequence that ends on i
        Deque<Integer> dq = new ArrayDeque<>();   // indexes, their dp values falling: the front is the best
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (!dq.isEmpty() && dq.peekFirst() < i - k)
                dq.pollFirst();                   // more than k back: too far to follow
            dp[i] = nums[i] + Math.max(0, dq.isEmpty() ? 0 : dp[dq.peekFirst()]);   // start afresh if it's better
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i])
                dq.pollLast();
            dq.offerLast(i);
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

var constrainedSubsetSum = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n).fill(0);         // dp[i]: the best sum of a subsequence that ends on i
    const dq = new Int32Array(n);            // indexes, their dp values falling: dq[head] is the best
    let head = 0, tail = 0, best = -Infinity;
    for (let i = 0; i < n; i++) {
        if (tail > head && dq[head] < i - k)
            head++;                          // more than k back: too far to follow
        dp[i] = nums[i] + Math.max(0, tail > head ? dp[dq[head]] : 0);   // start afresh if it's better
        while (tail > head && dp[dq[tail - 1]] <= dp[i])
            tail--;
        dq[tail++] = i;
        best = Math.max(best, dp[i]);
    }
    return best;
};

Complexity Analysis

Time Complexity: O(n)

Each index is pushed once and popped at most once.

Space Complexity: O(n)

The dp array and the deque.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Never starting fresh. dp[i] = x + (dp[dq[0]] if dq else 0)

On nums = [-5, 1], k = 1 it returns -4; the answer is 1. A subsequence may start at any index, so when every earlier sum within reach is negative, the best sum ending at i is nums[i] alone. Without max(0, …) this is Jump Game VI, which must start at index 0.

Returning the last dp. return dp[-1]

On nums = [9, -1, -1, -20], k = 1 it returns -13; the answer is 9. The subsequence doesn't have to end at the last index. The answer is the best dp value anywhere.

Ignoring the gap limit. positives = sum(x for x in nums if x > 0)

On nums = [4, -10, -10, -10, 4], k = 2 it returns 8; the answer is 4. Adding up every positive value (or taking the largest if none is positive) skips any number of indexes between two of them, but consecutive chosen indexes may be at most k apart.

Where This Pattern Is Taught

This problem practises a monotonic deque over earlier answers. It's taught in Monotonic Deque: the Window's Maximum, next to Jump Game VI, which uses the same recurrence without the fresh start.