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.
This approach involves using dynamic programming with a sliding window to maintain the maximum sum at each position. For each position i in the array, calculate the maximum sum that can be achieved till that position, considering the constraint j - i <= k. Use a deque to track the indices which offer the maximum sum within the range of k.
The solution uses a dynamic programming array to store the maximum sum possible up to each index. It utilizes a deque to maintain useful indices that help in calculating the needed maximum sum over the moving window of size k without having to recompute every time.
Time Complexity: O(n), where n is the number of elements in the array nums. The space complexity is O(n) due to the storage of the dp array and deque.
By using a priority queue (or heap), we manage the maximum possible sum within the constraint more efficiently. We employ dynamic programming to calculate the possible maximal sum at each index while maintaining a priority queue to keep track of the relevant maximum sums.
C implementation utilizes a priority queue structure to keep maximum subsequences track. Through a heap-push and heap-pop approach, the subset with the highest value is computed dynamically across the moving windows.
Time Complexity: O(n log k) primarily due to heap operations. Space Complexity: O(n) is utilized by the dp array and the heap.
We define f[i] to represent the maximum sum of the subsequence ending at nums[i] that meets the conditions. Initially, f[i] = 0, and the answer is max_{0 leq i \lt n} f(i).
We notice that the problem requires us to maintain the maximum value of a sliding window, which is a typical application scenario for a monotonic queue. We can use a monotonic queue to optimize the dynamic programming transition.
We maintain a monotonic queue q that is decreasing from the front to the back, storing the indices i. Initially, we add a sentinel 0 to the queue.
We traverse i from 0 to n - 1. For each i, we perform the following operations:
q[0] satisfies i - q[0] > k, it means the front element is no longer within the sliding window, and we need to remove the front element from the queue;f[i] = max(0, f[q[0]]) + nums[i], which means we add nums[i] to the sliding window to get the maximum subsequence sum;ans = max(ans, f[i]);i to the back of the queue and maintain the monotonicity of the queue. If f[q[back]] leq f[i], we need to remove the back element until the queue is empty or f[q[back]] > f[i].The final answer is ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sliding Window Maximum | Time Complexity: O(n), where n is the number of elements in the array |
| Dynamic Programming with Priority Queue (Heap) | Time Complexity: O(n log k) primarily due to heap operations. Space Complexity: O(n) is utilized by the dp array and the heap. |
| Dynamic Programming + Monotonic Queue | — |
| 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 |
Constrained Subsequence Sum - Leetcode 1425 - Python • NeetCodeIO • 9,482 views views
Watch 9 more video solutions →Practice Constrained Subsequence Sum with our built-in code editor and test cases.
Practice on FleetCode