DSA problem
Jump Game VI
You are given a 0-indexed integer array nums and an integer k. You start at index 0, and from any index i you may jump to any index in the range [i + 1, i + k] as long as it stays within the array. Your score is the sum of all nums[j] for the indices j you land on, including the starting index 0 and the final index n - 1. Return the maximum score you can obtain by reaching the last index.
This is naturally a dynamic programming problem. Define dp[i] as the best score achievable when standing on index i. The recurrence is dp[i] = nums[i] + max(dp[i - k], dp[i - k + 1], …, dp[i - 1]). A direct evaluation costs O(n * k) because each state inspects up to k previous states, which is too slow when both n and k reach 10^5.
The bottleneck is the sliding-window maximum over the most recent k DP values. This is exactly what a monotonic deque solves in amortized constant time per step. We maintain a deque of indices into dp whose values are kept in strictly decreasing order from front to back. The front of the deque is always the index of the maximum DP value within the current window of size k.
The optimal algorithm walks left to right computing each dp[i] using dp[front] as the window maximum, then enqueues i after evicting all back indices whose DP values are not greater than dp[i]. Indices that fall out of the window (i.e. front < i - k + 1 shifted appropriately) are removed from the front. The answer is dp[n - 1]. The total work is O(n) time and O(n) space.
Examples
nums = [1,-1,-2,4,-7,3], k = 27nums = [10,-5,-2,4,0,3], k = 317nums = [1,-5,-20,4,-1,3,-6,-3], k = 20Constraints
- 1 <= nums.length, k <= 10^5
- -10^4 <= nums[i] <= 10^4
- You must reach the last index starting from index 0.
- From index i you may jump to any index in [i + 1, min(i + k, n - 1)].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.