{x}
blog image

Constrained Subsequence Sum

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 <= 105
  • -104 <= nums[i] <= 104

Solution Explanation: Constrained Subsequence Sum

This problem asks for the maximum sum of a non-empty subsequence where consecutive elements are within a distance k of each other in the original array. A dynamic programming approach, enhanced with a monotonic deque for efficiency, is ideal.

Approach: Dynamic Programming with Monotonic Deque

  1. dp Array: We use a dp array where dp[i] stores the maximum sum of a subsequence ending at index i.

  2. Iteration: We iterate through the nums array. For each element nums[i]:

    • Sliding Window: We consider only the elements within a distance k to the left of nums[i]. This is our "sliding window".

    • Maximum from Window: We find the maximum value in dp within this sliding window. This represents the maximum sum achievable ending before nums[i].

    • Update dp[i]: We update dp[i] as the maximum of 0 (to handle negative values that may reduce overall sum) and (maximum from window) + nums[i].

  3. Monotonic Deque: A monotonic deque (decreasing from head to tail) is crucial for efficient windowed maximum finding. It stores indices, not values.

    • Deque Maintenance:

      • If an index in the deque is outside the current sliding window, it's removed from the head.
      • If the dp value at the back of the deque is less than or equal to dp[i], the back is popped (maintaining decreasing order).
      • i is then pushed to the back of the deque.

    • Efficiency: The deque's monotonic nature ensures that the head always holds the index with the maximum dp value within the sliding window, eliminating the need to iterate through the entire window for each i.

  4. Final Result: The maximum value in the dp array is the final answer.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of nums. The iteration happens once, and deque operations are O(1) on average.
  • Space Complexity: O(N) to store the dp array and the deque.

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples below demonstrate the solution using a monotonic deque to optimize the DP approach. Each example implements the core algorithm, emphasizing the deque's role in efficient maximum finding within the sliding window.

Note: The Go example uses a custom deque implementation (Deque) for demonstration. In other languages (Python, Java, C++), suitable deque data structures are readily available. For TypeScript, a Deque class is implemented for clarity.

(Code examples as provided in the original response)

Summary

The combination of dynamic programming and a monotonic deque provides an efficient O(N) solution for this problem. The deque effectively manages the sliding window, drastically reducing the time complexity compared to a naive approach that would iterate through the window in each step, resulting in an O(N*k) solution.