Constrained Subsequence Sum

hard monotonic deque dp

Problem

You are given an integer array nums (values may be negative) and a positive integer k. Pick a non-empty subsequence (keep original order) so that any two picks that end up adjacent in the subsequence come from indices at most k apart in nums. Return the largest possible sum of the picked values.

Think of it as Kadane with a gap limit: dp[i] = nums[i] + max(0, max(dp[i−k..i−1])). A monotonic decreasing deque serves that sliding-window maximum in O(1) per index, since n can be up to 10⁵.

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

Output37

Pick indices 0, 1, 3, 4 (values 10 + 2 + 5 + 20 = 37); every consecutive pair of picks is at most 2 indices apart, and -10 is skipped.

nums (comma-separated integers)

k (max index gap)

from collections import deque

def constrained_subset_sum(nums, k):
    n = len(nums)
    dp = [0] * n
    dq = deque()                 # indices, dp decreasing
    best = float('-inf')
    for i in range(n):
        while dq and dq[0] < i - k:
            dq.popleft()         # left the window
        dp[i] = nums[i] + max(dp[dq[0]] if dq else 0, 0)
        best = max(best, dp[i])
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()             # dominated by dp[i]
        dq.append(i)
    return best

function constrainedSubsetSum(nums, k) {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  const dq = []; // indices, dp decreasing
  let best = -Infinity;
  for (let i = 0; i < n; i++) {
    while (dq.length && dq[0] < i - k) {
      dq.shift(); // left the window
    }
    dp[i] = nums[i] + Math.max(dq.length ? dp[dq[0]] : 0, 0);
    best = Math.max(best, dp[i]);
    while (dq.length && dp[dq[dq.length - 1]] <= dp[i]) {
      dq.pop(); // dominated by dp[i]
    }
    dq.push(i);
  }
  return best;
}

int constrainedSubsetSum(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    Deque<Integer> dq = new ArrayDeque<>(); // indices, dp decreasing
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - k) {
            dq.pollFirst(); // left the window
        }
        int carry = dq.isEmpty() ? 0 : Math.max(dp[dq.peekFirst()], 0);
        dp[i] = nums[i] + carry;
        best = Math.max(best, dp[i]);
        while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) {
            dq.pollLast(); // dominated by dp[i]
        }
        dq.addLast(i);
    }
    return best;
}

int constrainedSubsetSum(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    deque<int> dq; // indices, dp decreasing
    int best = INT_MIN;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() < i - k) {
            dq.pop_front(); // left the window
        }
        int carry = dq.empty() ? 0 : max(dp[dq.front()], 0);
        dp[i] = nums[i] + carry;
        best = max(best, dp[i]);
        while (!dq.empty() && dp[dq.back()] <= dp[i]) {
            dq.pop_back(); // dominated by dp[i]
        }
        dq.push_back(i);
    }
    return best;
}

Explanation

Define dp[i] as the best sum of a valid subsequence that ends exactly at index i. The previous pick (if any) must sit in the window [i−k, i−1], so dp[i] = nums[i] + max(0, max(dp[i−k..i−1])). The max(…, 0) is the Kadane move: if every reachable predecessor is negative, start a fresh subsequence at i instead of dragging the loss along.

Evaluating max(dp[i−k..i−1]) naively costs O(k) per index, O(nk) overall — too slow for n = 10⁵. The fix is the classic sliding-window maximum deque: keep indices whose dp values are decreasing from front to back. The front is always the window maximum. Before using it, drop fronts older than i − k; after computing dp[i], pop every back whose dp is ≤ dp[i] — those values are both older and no larger, so they can never be a better choice than dp[i] — then push i.

Walking the default example nums = [10, 2, -10, 5, 20], k = 2: dp[0] = 10. dp[1] = 2 + max(10, 0) = 12, and 10 gets popped because 12 dominates it. dp[2] = −10 + 12 = 2 (the deque stays [12, 2]). dp[3] = 5 + 12 = 17, which pops both 2 and 12. dp[4] = 20 + 17 = 37, which pops 17. The answer is the largest dp seen, 37 — exactly the picks 10, 2, 5, 20 with −10 skipped.

Note dp[2] = 2 still matters even though it includes the −10: had the array continued, index 2 might have been the only bridge inside someone's window. The deque keeps it precisely until something newer and at least as good (dp[3] = 17) makes it pointless.

Each index is pushed once and popped at most once (from one end or the other), so all deque work is amortized O(1) per element: O(n) time total. The dp array and deque need O(n) space (the deque alone is O(k), but dp dominates). The answer is max(dp), tracked on the fly in best, because the optimal subsequence has to end somewhere.

Time: O(n) Space: O(n)