Constrained Subsequence Sum
Hard · Stack & Strings · Array · Dynamic Programming · Queue · Sliding Window · Monotonic Queue · Heap (Priority Queue)
Problem
Given an integer array nums and an integer k, choose a non-empty subsequence of nums such that for every two consecutive chosen elements nums[i] and nums[j] (with i < j), the gap satisfies j - i <= k.
Return the largest possible sum of such a subsequence. A subsequence keeps the original order but may skip elements.
Examples
Input: nums = [5,-3,-4,6,2], k = 2 Output: 10
Take 5, -3, 6 and 2: each gap is at most 2, giving 10. Skipping -3 too would leave a gap of 3.
Input: nums = [-4,-1,-7], k = 1 Output: -1
The best non-empty choice is just -1.
Input: nums = [3,-9,-9,4], k = 3 Output: 7
3 and 4 are exactly 3 apart, so both can be taken: 7.
Constraints
- 1 <= k <= len(nums) <= 10^5
- -10^4 <= nums[i] <= 10^4
Approaches
- Baseline: scan the last k entries — time O(n · k), space O(n)
Follow-up
The recurrence is a sliding-window maximum over its own results, which the monotonic deque answers as they are produced. The use cases reverse the gap rule (picks at least k apart) and switch to contiguous blocks of at most k values.
Related problems
Start free on Cariara · Coding problems · System design studio
