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] <= 104The Constrained Subsequence Sum problem asks for the maximum sum of a subsequence where the distance between consecutive chosen elements is at most k. A natural way to approach this is with dynamic programming, where dp[i] represents the maximum subsequence sum ending at index i. The transition considers the best dp[j] from the previous k positions and adds the current value.
However, scanning the previous k values for every index would lead to O(nk) time. To optimize this, we maintain a monotonic deque that keeps candidate indices with the highest dp values within the valid window. This allows us to quickly access the best previous value and efficiently discard outdated or smaller candidates.
This sliding window + monotonic queue strategy reduces the complexity to O(n) time with O(n) space. Alternative implementations can use a max heap (priority queue), though they are typically slightly slower.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming + Monotonic Deque | O(n) | O(n) |
| Dynamic Programming + Max Heap | O(n log k) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming.
Let dp[i] be the solution for the prefix of the array that ends at index i, if the element at index i is in the subsequence.
dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])
Use a heap with the sliding window technique to optimize the dp.
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.
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.
1#include <iostream>
2#include <vector>
3#include <deque>
4using namespace std;
5
6int constrainedSubsequenceSum(vector<int>& nums, int k) {
7 vector<int> dp(nums.size(), 0);
8 deque<int> deq;
9 int maxSum = nums[0];
10 dp[0] = nums[0];
11 deq.push_back(0);
12
13 for (int i = 1; i < nums.size(); ++i) {
14 if (!deq.empty() && deq.front() < i - k) {
deq.pop_front();
}
dp[i] = nums[i] + (deq.empty() ? 0 : dp[deq.front()]);
maxSum = max(maxSum, dp[i]);
while (!deq.empty() && dp[deq.back()] <= dp[i]) {
deq.pop_back();
}
deq.push_back(i);
}
return maxSum;
}
int main() {
vector<int> nums = {10, 2, -10, 5, 20};
int k = 2;
cout << constrainedSubsequenceSum(nums, k) << endl;
return 0;
}This solution implements a C++ version using vectors and deques. The deque keeps track of indices with potential maximum sums, helping compute the current index's maximum sum efficiently.
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.
Time Complexity: O(n log k) primarily due to heap operations. Space Complexity: O(n) is utilized by the dp array and the heap.
1#include <vector>
#include <queue>
using namespace std;
int constrainedSubsequenceSum(vector<int>& nums, int k) {
priority_queue<pair<int, int>> pq;
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
pq.push({nums[0], 0});
int maxSum = nums[0];
for (int i = 1; i < nums.size(); ++i) {
while (!pq.empty() && pq.top().second < i - k) {
pq.pop();
}
int sum = nums[i];
if (!pq.empty()) {
sum += pq.top().first;
}
dp[i] = sum;
pq.push({dp[i], i});
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
int main() {
vector<int> nums = {10, 2, -10, 5, 20};
int k = 2;
cout << constrainedSubsequenceSum(nums, k) << endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, a max heap (priority queue) can track the best DP value from the previous k indices. However, heap operations introduce a log(k) factor, making it slightly slower than the monotonic deque solution.
Yes, this problem reflects common interview patterns involving dynamic programming with sliding window optimization. Variants of this technique frequently appear in FAANG and other top tech company interviews.
A monotonic queue (implemented with a deque) is the most efficient data structure for this problem. It keeps candidate DP values in decreasing order while ensuring indices stay within the valid window of size k.
The optimal approach uses dynamic programming combined with a monotonic deque. It maintains the maximum DP value within the last k indices, allowing each element to be processed in constant time. This results in an overall time complexity of O(n).
C++ uses a max-heap (priority queue) to track potential maxima. It provides a compact way to check out the maximums across a moving window efficiently.