Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence such that for every pair of consecutive elements in the subsequence, their indices differ by at most k. Example: Input: nums = [10,2,-10,5,20], k = 2 Output: 37 Explanation: The subsequence [10,2,5,20] is valid and has sum 37. Pattern focus: Monotonic Deque for dynamic window maximum.
nums = array of integers, k = maximum index gap between consecutive chosen elements
maximum constrained subsequence sum
Example 1:
Input:
nums = [10,2,-10,5,20] k = 2
Output:
37
Explanation:
The deque tracks the best dp values within the last k positions.
Example 2:
Input:
nums = [-1,-2,-3] k = 1
Output:
-1
Explanation:
Choosing a single element is allowed, so the best answer is the largest number.