641. Jump Game VI
You stand on index 0 of an integer array nums (values may be negative) and you are given a positive integer k. From index i you may hop forward to any index i + 1 through i + k (without leaving the array). Every index you land on — including index 0 where you start — adds nums[index] to your score.
You must end on the last index. Return the maximum total score you can collect along the way.
Example 1:
Input: nums = [1, -1, -2, 4, -7, 3], k = 2
Output: 7
Explanation: Visit indices 0 → 1 → 3 → 5, collecting 1 + (−1) + 4 + 3 = 7. Detouring through −2 or −7 only loses points.
Example 2:
Input: nums = [10, -5, -2, 4, 0, 3], k = 3
Output: 17
Explanation: Hop 0 → 3 → 4 → 5 (or 0 → 3 → 5): 10 + 4 + 0 + 3 = 17.
Example 3:
Input: nums = [1, -5, -20, 4, -1, 3, -6, -3], k = 2
Output: 0
Explanation: The best route is 0 → 1 → 3 → 5 → 7: 1 − 5 + 4 + 3 − 3 = 0. Every path must eat some negatives here.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- 1 ≤ k ≤ nums.length
- -10⁴ ≤ nums[i] ≤ 10⁴
Hints:
Define dp[i] as the best score of any valid path from index 0 that ends exactly on index i. Then dp[i] = nums[i] + max(dp[i−k] … dp[i−1]).
Computing that max by scanning k previous entries gives O(n·k) — too slow when both are 10^5. The subproblem is really a sliding-window maximum.
A deque that keeps indices of dp values in decreasing order answers "max of the last k dp entries" in O(1): pop expired indices from the front, pop dominated ones from the back.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, -1, -2, 4, -7, 3], k = 2
Expected output: 7