Problem

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Examples

Example 1:

Input:
nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].
The possible subsequences satisfying the conditions are:
- [10, 2] with sum 12
- [10, 2, 5] with sum 17
- [10, 2, 5, 20] with sum 37
- [10, 5, 20] with sum 35
- [2, 5, 20] with sum 27
Among these, the subsequence [10, 2, 5, 20] has the maximum sum of 37.

Example 2:

Input:
nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input:
nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

Solution

Method 1 - Using DP and Sliding window

Here are the steps:

  • Initialisation: Create an array dp where dp[i] represents the maximum sum of a subsequence ending at index i. The result is initialised with the values of the nums array since the minimum subsequence ending at each index is the element itself.
  • Deque for Sliding Window Maximum: Use a deque to keep track of indices where dp values are potential candidates for forming a valid subsequence ending at a current element.
  • Iterate through the Array: For each element in nums, update dp[i] by considering the maximum dp[j] where i - k <= j < i.
  • Update Deque: Maintain the deque in such a way that the values in dp are in decreasing order. If the current index i makes the oldest value in the deque invalid (i.e., i - k > j), remove it from the deque.
  • Compute the Result: The result is the maximum value in the dp array.

Code

Java
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        if (n == 0)
            return 0;

        // Initialize dp array
        int[] dp = new int[n];
        System.arraycopy(nums, 0, dp, 0, n);

        // Deque to store indices of potential maximums for dp array
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // Remove elements not within sliding window of size k
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }

            // Update dp[i] using the maximum value in dp[deque]
            if (!deque.isEmpty()) {
                dp[i] += dp[deque.peekFirst()];
            }

            // Maintain deque: remove elements from the deque that are smaller
            // than current dp[i]
            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
                deque.pollLast();
            }

            // Add current index to the deque
            deque.offerLast(i);
        }

        // The result is the maximum value in dp array
        int result = dp[0];
        for (int i = 1; i < n; i++) {
            result = Math.max(result, dp[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {10, 2, -10, 5, 20};
        int k = 2;
        System.out.println(sol.constrainedSubsetSum(
            nums, k)); // Output should be 37 (subsequence [10, 2, 5, 20])
    }
}
Python
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if n == 0:
            return 0

        # Initialize dp array
        dp = nums[:]

        # Deque to store indices of potential maximums for dp array
        dq = deque()

        for i in range(n):
            # Remove elements not within sliding window of size k
            while dq and dq[0] < i - k:
                dq.popleft()

            # Update dp[i] using the maximum value in dp[dq]
            if dq:
                dp[i] += dp[dq[0]]

            # Maintain deque: remove elements from the deque that are smaller than current dp[i]
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()

            # Add current index to the deque
            dq.append(i)

        # The result is the maximum value in dp array
        return max(dp)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the nums array.
    • Initialising the dp array takes O(n) time.
    • For each element, we may potentially remove elements from both ends of the deque at most once, and we add elements to the deque.
    • Each element is added and removed from the deque at most once.
  • 🧺 Space complexity: O(n)
    • Space for dp array: Requires O(n).
    • Space for Deque: In the worst case, the deque can hold at most k elements, but this is still bounded by O(n) if considering the entire array.