Watch 10 video solutions for Constrained Subsequence Sum, a hard level problem involving Array, Dynamic Programming, Queue. This walkthrough by NeetCodeIO has 9,482 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 104Problem Overview: Given an integer array nums and an integer k, choose a subsequence such that the difference between consecutive chosen indices is at most k. The goal is to maximize the subsequence sum.
Approach 1: Dynamic Programming (Brute Window Scan) (Time: O(nk), Space: O(n))
Define dp[i] as the maximum subsequence sum that ends at index i. To compute it, look at the previous k positions and extend the best subsequence: dp[i] = nums[i] + max(0, dp[i-k...i-1]). This requires scanning up to k elements for every index. The approach demonstrates the core dynamic programming transition but becomes slow when k is large because every step performs a window maximum search.
Approach 2: Dynamic Programming with Priority Queue (Heap) (Time: O(n log k), Space: O(n))
Replace the repeated window scan with a max heap storing pairs (dp value, index). While iterating through the array, remove heap entries whose index is more than k behind the current position. The heap top always gives the largest valid dp value within the window. Compute dp[i] = nums[i] + max(0, top), then push the new state back into the heap. This reduces the lookup cost to log k while maintaining the sliding window constraint.
Approach 3: Dynamic Programming with Sliding Window Maximum (Monotonic Deque) (Time: O(n), Space: O(n))
The optimal approach maintains the window maximum using a monotonic deque. Store indices of dp values in decreasing order so the front always holds the maximum candidate. Before processing index i, remove indices outside the k window. Compute dp[i] = nums[i] + max(0, dp[deque front]). After computing dp[i], remove smaller values from the back of the deque to preserve decreasing order and push i. Each index enters and leaves the deque once, producing linear time. This technique combines dynamic programming with a sliding window maximum implemented using a monotonic queue.
Recommended for interviews: Interviewers typically expect the monotonic deque solution with O(n) time. Explaining the dp[i] = nums[i] + max(0, best previous) transition first shows understanding of the problem. Improving the window maximum using a deque demonstrates strong knowledge of sliding window optimization and queue-based data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Window Scan | O(nk) | O(n) | Conceptual baseline to understand the DP transition |
| DP with Priority Queue (Heap) | O(n log k) | O(n) | When a heap is easier to implement than a deque |
| DP with Monotonic Deque (Sliding Window Maximum) | O(n) | O(n) | Optimal solution for large inputs and typical interview expectation |