Constrained Subsequence Sum
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
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
dparray of sizen, wherenis the length ofnums. - Initialize a variable
maxSumtoInteger.MIN_VALUEto keep track of the final result. - Iterate through the array with an index
ifrom0ton-1:- For each
i, find the maximum value among the previouskDP states. Let's call thismaxPrev. InitializemaxPrevto0. - Iterate with an index
jfrommax(0, i - k)toi - 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]).
- For each
- After the outer loop finishes, return
maxSum.
Walkthrough
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
Time
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
O(n) - We use an auxiliary `dp` array of the same size as the input array.
Trade-offs
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.
To optimize the brute-force DP, we can speed up the process of finding the maximum value in the sliding window of the last k elements. A max heap (or Priority Queue) is a suitable data structure for this task. The heap will store the dp values calculated so far, allowing us to retrieve the maximum in O(log k) time.
Algorithm
- Initialize a
dparray of sizen. - Initialize a max heap (Priority Queue in Java) to store pairs of
[value, index]. - Initialize
maxSumtoInteger.MIN_VALUE. - Loop
ifrom0ton-1:- Remove elements from the top of the heap whose indices are outside the valid window (
index < i - k). - Determine the maximum previous sum,
maxPrev. If the heap is not empty,maxPrevisheap.peek()[0]. We takemax(0, maxPrev). - Calculate
dp[i] = nums[i] + maxPrev. - Add the new pair
[dp[i], i]to the heap. - Update
maxSum = max(maxSum, dp[i]).
- Remove elements from the top of the heap whose indices are outside the valid window (
- Return
maxSum.
Walkthrough
The DP recurrence relation remains the same: dp[i] = nums[i] + max(0, max_in_window). The optimization comes from how we find max_in_window.
We use a max heap that stores pairs of (value, index), ordered by value. As we iterate through the array from i = 0 to n-1:
- We first check the top of the heap. If its index is outside the current window (i.e.,
index < i - k), we remove it. We repeat this until the top of the heap is a valid predecessor. - Now, the maximum value in the window is at the top of the heap. We retrieve this value to calculate
dp[i]. - After computing
dp[i], we insert the new pair(dp[i], i)into the heap. - We continuously track the overall maximum
dpvalue to find our final answer.
This reduces the time to find the maximum in the window from O(k) to O(log k), improving the overall time complexity.
import java.util.PriorityQueue; class Solution { public int constrainedSubsetSum(int[] nums, int k) { int n = nums.length; int[] dp = new int[n]; // Max heap storing pairs of [value, index] PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]); int maxSum = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { // Remove elements from heap that are out of the window [i-k, i-1] while (!heap.isEmpty() && heap.peek()[1] < i - k) { heap.poll(); } int maxPrev = 0; if (!heap.isEmpty()) { maxPrev = Math.max(0, heap.peek()[0]); } dp[i] = nums[i] + maxPrev; heap.offer(new int[]{dp[i], i}); maxSum = Math.max(maxSum, dp[i]); } return maxSum; }}Complexity
Time
O(n log k) - The main loop runs `n` times. Inside the loop, heap operations (insertion and deletion) take `O(log k)` time, as the heap's size is bounded by `k`.
Space
O(n) - The `dp` array requires O(n) space, and the heap can store up to `k` elements, so it requires O(k) space. The total is O(n).
Trade-offs
Pros
Significantly more efficient than the brute-force DP approach.
Passes the time limits for the given constraints on most platforms.
Cons
The
log kfactor makes it slower than the optimal linear-time solution.Requires O(n) extra space for the DP array, which is less space-efficient than the optimal approach.
This is the most optimal solution, achieving linear time complexity. It refines the dynamic programming approach by using a monotonic deque to solve the 'Sliding Window Maximum' subproblem efficiently. The deque stores indices of candidates for the maximum value in the current window [i-k, i-1], ensuring that finding this maximum takes amortized O(1) time.
Algorithm
- Initialize a deque (double-ended queue) to store indices.
- Initialize
maxSumtoInteger.MIN_VALUE. - Iterate
ifrom0ton-1:- If the deque is not empty, the maximum value in the current window is at the front of the deque. Let
prevMax = nums[deque.peekFirst()]. - Calculate the current DP value by updating
nums[i]in-place: ifprevMax > 0,nums[i] += prevMax. - Update the overall
maxSum = Math.max(maxSum, nums[i]). - To maintain the deque's monotonic property, remove indices from the end of the deque whose
numsvalues are less than or equal to the currentnums[i]. - Add the current index
ito the end of the deque. - Remove the index from the front of the deque if it's now outside the window of size
k(i.e.,i - deque.peekFirst() >= k).
- If the deque is not empty, the maximum value in the current window is at the front of the deque. Let
- Return
maxSum.
Walkthrough
We maintain a deque of indices j such that the corresponding DP values (dp[j]) are in decreasing order. This means the index corresponding to the maximum value in the current window is always at the front of the deque.
For each index i from 0 to n-1, we perform the following steps:
- Find Window Max: The maximum
dpvalue in the window[i-k, i-1]is simplydp[deque.peekFirst()](if the deque is not empty). - Calculate
dp[i]: We calculatedp[i]using the value from step 1. To save space, we can store thedpvalues in the inputnumsarray itself. So,nums[i]becomesnums[i] + max(0, nums[deque.peekFirst()]). - Maintain Monotonicity: Before adding
ito the deque, we pop indices from the back of the deque as long as their correspondingdpvalues are less than or equal todp[i]. This ensures the decreasing order property is preserved. - Update Window: We remove the index from the front of the deque if it falls out of the
k-sized window (i.e.,deque.peekFirst() <= i - k).
By doing this, each index is pushed and popped from the deque at most once, leading to an overall linear time complexity.
import java.util.ArrayDeque;import java.util.Deque; class Solution { public int constrainedSubsetSum(int[] nums, int k) { int n = nums.length; // Deque will store indices j such that nums[j] (which represents dp[j]) // are in decreasing order. Deque<Integer> deque = new ArrayDeque<>(); int maxSum = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { // Get previous max from the window int prevMax = 0; if (!deque.isEmpty()) { prevMax = nums[deque.peekFirst()]; } // Calculate dp[i] (in-place in nums array) if (prevMax > 0) { nums[i] += prevMax; } maxSum = Math.max(maxSum, nums[i]); // Maintain monotonic property of the deque while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } deque.offerLast(i); // Maintain window size if (i - deque.peekFirst() >= k) { deque.pollFirst(); } } return maxSum; }}Complexity
Time
O(n) - Each element's index is added to and removed from the deque at most once. All operations inside the loop are amortized O(1).
Space
O(k) - The deque will store at most `k+1` indices. By modifying the input array in-place, we avoid the need for a separate O(n) `dp` array.
Trade-offs
Pros
Optimal time complexity.
Space-efficient, especially with the in-place modification which reduces extra space to O(k).
Cons
The logic for maintaining the monotonic deque can be more complex to grasp and implement correctly compared to the heap-based solution.
Solutions
Solution
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; }}class Solution {public: int constrainedSubsetSum(vector<int> &nums, int k) { int n = nums.size(); vector<int> dp(n); int ans = INT_MIN; deque<int> q; for (int i = 0; i < n; ++i) { if (!q.empty() && i - q.front() > k) q.pop_front(); dp[i] = max(0, q.empty() ? 0 : dp[q.front()]) + nums[i]; ans = max(ans, dp[i]); while (!q.empty() && dp[q.back()] <= dp[i]) q.pop_back(); q.push_back(i); } return ans; }};class Solution: def constrainedSubsetSum(self, nums: List[int], k: int) -> int: n = len(nums) dp = [0] * n ans = - inf q = deque() for i, v in enumerate(nums): if q and i - q[0] > k: q . popleft() dp[i] = max(0, 0 if not q else dp[q[0]]) + v while q and dp[q[- 1]] <= dp[i]: q . pop() q . append(i) ans = max(ans, dp[i]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.