Description
Given an integer array nums and integer k, return the maximum sum of a non-empty subsequence where consecutive elements in the original array differ by at most k indices.
Examples
Input:
nums = [10,2,-10,5,20], k = 2Output:
37Explanation:
Subsequence [10,2,5,20] at indices 0,1,3,4 has gaps within k=2, summing to 37.
Input:
nums = [-1,-2,-3], k = 1Output:
-1Explanation:
All values are negative. Since the subsequence must be non-empty, the best choice is the maximum single element: -1.
Input:
nums = [1, -5, 8, -3, 12, 6], k = 3Output:
27Explanation:
The subsequence [1, 8, 12, 6] at indices [0, 2, 4, 5] skips negative values while keeping consecutive index gaps ≤ k=3.
Constraints
- •
1 ≤ k ≤ nums.length ≤ 10⁵