Problem Description

Given an integer array nums and an integer k, you are asked to find the maximum sum of a non-empty subsequence of nums such that for every pair of consecutive elements in the subsequence, their indices in nums differ by at most k. In other words, for a chosen subsequence with indices i_1, i_2, ..., i_m, it must be true that 1 ≤ i_{j+1} - i_j ≤ k for all valid j. Each element from nums can be used at most once, and you must select at least one element.

• Input: An integer array nums and an integer k.
• Output: The maximum sum of a constrained subsequence as defined above.
• Constraints:
  • You cannot reuse elements.
  • There is always at least one valid answer (since you can pick one element).
  • Indices in the chosen subsequence must be within k of each other.

Thought Process

At first glance, this problem looks similar to the classic "maximum subarray sum" problem, but with an added twist: when picking elements to form the subsequence, we can only choose the next number within k indices of the current one.

A brute-force approach would be to try every possible subsequence that fits the constraints, but this quickly becomes infeasible for large arrays due to the exponential number of possibilities. Instead, we need to find a way to efficiently compute, for each position, the best sum we can achieve ending at that position, considering the constraint on indices.

This hints at using dynamic programming, where for each index, we store the maximum sum of a valid subsequence ending at that index. The challenge is to efficiently find the best previous sum within the last k indices, which leads us to consider data structures that support fast maximum queries in a sliding window.

Solution Approach

We solve the problem using dynamic programming and a monotonic deque to maintain the maximum in a sliding window.

1. Dynamic Programming State:
   • Let dp[i] be the maximum sum of a valid constrained subsequence ending at index i.
   • We initialize dp[i] = nums[i] because we can always start a new subsequence with just nums[i].
2. Transition:
   • For each i, to extend a subsequence, we look at dp[j] for all j in [i-k, i-1] and pick the maximum. Then dp[i] = nums[i] + max(0, max(dp[j])).
   • The max(0, ...) is because we can always start fresh at i if all previous sums are negative.
3. Optimizing the Transition:
   • Naively, for each i, looking back k steps is O(k), resulting in O(nk) time.
   • We use a monotonic deque to keep track of the indices of the largest dp values in the last k steps. This allows us to get the maximum in O(1) time per step, and maintain the deque in amortized O(1) per step.
4. Result:
   • The answer is the maximum value in dp.

This approach is efficient and leverages the properties of sliding windows and monotonic queues for optimal performance.

Example Walkthrough

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

1. Initialization: dp[0] = 10
2. Index 1:
   • Look back at dp[0] (within k=2): max = 10
   • dp[1] = nums[1] + max(0, 10) = 2 + 10 = 12
3. Index 2:
   • Look back at dp[0], dp[1] (within k=2): max = 12
   • dp[2] = -10 + max(0, 12) = 2
4. Index 3:
   • Look back at dp[1], dp[2] (within k=2): max = 12
   • dp[3] = 5 + max(0,12) = 17
5. Index 4:
   • Look back at dp[2], dp[3] (within k=2): max = 17
   • dp[4] = 20 + max(0,17) = 37

The answer is 37, achieved by the subsequence [10,2,5,20] (indices 0,1,3,4).

Time and Space Complexity

• Brute-force:
  • Time: Exponential, as you would need to check all possible subsequences.
  • Space: O(n) for recursion stack or storing subsequences.
• Optimized (DP + Monotonic Deque):
  • Time: O(n), since each element is added and removed from the deque at most once.
  • Space: O(n), for the dp array and the deque (which never holds more than k elements).

The use of the deque ensures that finding the sliding window maximum is efficient, avoiding redundant comparisons.

Summary

The "Constrained Subsequence Sum" problem requires finding the maximum sum of a subsequence where consecutive elements are at most k apart. A naive approach is too slow, but by recognizing the structure of the problem, we use dynamic programming and a monotonic queue to efficiently track the maximum sum for each possible endpoint. This approach elegantly combines classic DP with advanced data structures, resulting in an O(n) solution that is both fast and easy to understand once the core ideas are clear.

Code Implementation

from collections import deque

class Solution:
    def constrainedSubsetSum(self, nums, k):
        n = len(nums)
        dp = nums[:]
        dq = deque()
        res = nums[0]
        for i in range(n):
            # Remove indices out of window
            if dq and dq[0] < i - k:
                dq.popleft()
            # If dq not empty, add max in window
            if dq:
                dp[i] = max(dp[i], nums[i] + dp[dq[0]])
            # Maintain decreasing order in dq
            while dq and dp[dq[-1]] < dp[i]:
                dq.pop()
            dq.append(i)
            res = max(res, dp[i])
        return res
      

#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(nums);
        deque<int> dq;
        int res = nums[0];
        for (int i = 0; i < n; ++i) {
            if (!dq.empty() && dq.front() < i - k)
                dq.pop_front();
            if (!dq.empty())
                dp[i] = max(dp[i], nums[i] + dp[dq.front()]);
            while (!dq.empty() && dp[dq.back()] < dp[i])
                dq.pop_back();
            dq.push_back(i);
            res = max(res, dp[i]);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = Arrays.copyOf(nums, n);
        Deque<Integer> dq = new ArrayDeque<>();
        int res = nums[0];
        for (int i = 0; i < n; i++) {
            if (!dq.isEmpty() && dq.peekFirst() < i - k)
                dq.pollFirst();
            if (!dq.isEmpty())
                dp[i] = Math.max(dp[i], nums[i] + dp[dq.peekFirst()]);
            while (!dq.isEmpty() && dp[dq.peekLast()] < dp[i])
                dq.pollLast();
            dq.offerLast(i);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
      

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var constrainedSubsetSum = function(nums, k) {
    const n = nums.length;
    const dp = nums.slice();
    const dq = [];
    let res = nums[0];
    for (let i = 0; i < n; i++) {
        // Remove indices out of the window
        if (dq.length && dq[0] < i - k) dq.shift();
        if (dq.length) dp[i] = Math.max(dp[i], nums[i] + dp[dq[0]]);
        while (dq.length && dp[dq[dq.length - 1]] < dp[i]) dq.pop();
        dq.push(i);
        res = Math.max(res, dp[i]);
    }
    return res;
};