Constrained Subsequence Sum

HARD

Description

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.

Example 1:

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

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].

Constraints:

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Approaches

Checkout 3 different approaches to solve Constrained Subsequence Sum. Click on different approaches to view the approach and algorithm in detail.

Brute-force Dynamic Programming

This approach uses a straightforward dynamic programming solution. We define dp[i] as the maximum sum of a valid subsequence ending at index i. To compute dp[i], we must include nums[i]. The previous element in the subsequence, say nums[j], must satisfy the condition j - i <= k. Therefore, dp[i] is nums[i] plus the maximum dp[j] over the valid range of j (i.e., i - k <= j < i). If all possible previous subsequence sums are negative, it's better to start a new subsequence from nums[i], so we take the maximum of 0 and the previous maximum sum.

Algorithm

Initialize a dp array of size n, where n is the length of nums.
Initialize a variable maxSum to Integer.MIN_VALUE to keep track of the final result.
Iterate through the array with an index i from 0 to n-1:
- For each i, find the maximum value among the previous k DP states. Let's call this maxPrev. Initialize maxPrev to 0.
- Iterate with an index j from max(0, i - k) to i - 1.
- In the inner loop, update maxPrev = Math.max(maxPrev, dp[j]).
- After the inner loop, calculate dp[i] = nums[i] + maxPrev.
- Update the overall maximum: maxSum = Math.max(maxSum, dp[i]).
After the outer loop finishes, return maxSum.

We create a dp array of the same size as nums. dp[i] will store the maximum constrained subsequence sum that ends with the element nums[i]. The core of the algorithm is the recurrence relation:

dp[i] = nums[i] + max(0, max(dp[j])) for all j such that i - k <= j < i.

We can implement this by iterating through the nums array from i = 0 to n-1. For each i, we have a nested loop that scans the previous k elements (from j = i-1 down to i-k) to find the maximum dp value in that window. This maximum value is then added to nums[i] to compute dp[i]. The final answer is the maximum value found in the dp array, as the subsequence is not required to end at the last element of the array.

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int maxPrev = 0;
            for (int j = Math.max(0, i - k); j < i; j++) {
                maxPrev = Math.max(maxPrev, dp[j]);
            }
            dp[i] = nums[i] + maxPrev;
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

Complexity Analysis

Time Complexity: O(n * k) - For each element `i` in the input array, we iterate up to `k` previous elements to find the maximum. This results in a nested loop structure.Space Complexity: O(n) - We use an auxiliary `dp` array of the same size as the input array.

Pros and Cons

Pros:

Simple to understand and implement.
Correctly models the problem's state transitions.

Cons:

Highly inefficient for large inputs due to the nested loops.
Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Constrained Subsequence Sum. Click on different languages to view the code.

class Solution {
public
  int constrainedSubsetSum(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    int ans = Integer.MIN_VALUE;
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      if (!q.isEmpty() && i - q.peek() > k) {
        q.poll();
      }
      dp[i] = Math.max(0, q.isEmpty() ? 0 : dp[q.peek()]) + nums[i];
      while (!q.isEmpty() && dp[q.peekLast()] <= dp[i]) {
        q.pollLast();
      }
      q.offer(i);
      ans = Math.max(ans, dp[i]);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Constrained Subsequence Sum

Patterns:

Sliding WindowDynamic Programming

Data Structures:

ArrayHeap (Priority Queue)QueueMonotonic Queue

Companies:

Akuna Capital |