DSA problem
Constrained Subsequence Sum
Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of nums such that for every two consecutive integers in the subsequence at positions i and j (with i < j), we have j - i <= k. A subsequence preserves the original relative order but does not need to be contiguous.
Define dp[i] as the best sum of a valid subsequence ending exactly at index i. The transition is dp[i] = nums[i] + max(0, max(dp[i - k], dp[i - k + 1], …, dp[i - 1])). The "max with 0" reflects the freedom to start a fresh subsequence at i if every earlier candidate is negative.
A naive O(n * k) inner loop is too slow when n and k are both 10^5. The bottleneck — once again — is a sliding-window maximum over the last k DP values. This is a perfect fit for a monotonic decreasing deque of indices into dp. The deque's front holds the index of the maximum DP value within the window.
The algorithm walks left to right. For each index i, drop deque fronts whose indices are less than i - k (out of window). Compute dp[i] = nums[i] + max(0, dp[deque.front]) (or just nums[i] if the deque is empty). Then pop back entries whose DP values are less than or equal to dp[i] and push i. Track the running maximum DP value to return. Total time is O(n), space is O(n).
Examples
nums = [10,2,-10,5,20], k = 237nums = [-1,-2,-3], k = 1-1nums = [10,-2,-10,-5,20], k = 223Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- A subsequence is a sequence that preserves original order but can skip elements.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.