Jump Game VI
Problem
0 of an integer array nums and must
reach the last index. From index i you may jump forward to any index in
[i + 1, i + k] (staying inside the array). Your score is the sum of
nums over every index you land on, including the first and last. Return the
maximum achievable score.nums = [1,-1,-2,4,-7,3], k = 2Output7 (1 → -1 → 4 → 3)nums = [10,-5,-2,4,0,3], k = 3Output17nums = [1,-5,-20,4,-1,3,-6,-3], k = 2Output01 ≤ n, k ≤ 105 · -104 ≤ nums[i] ≤ 104
Try it yourself
class Solution {
public int maxResult(int[] nums, int k) {
}
}
dp[i] = nums[i] + max(dp[i-k..i-1]) — a sliding window
maximum over the dp array. A deque of indices with decreasing dp values gives that
maximum in O(1) amortized per step.Instinct Arrival order matters, or you need the max/min of a moving window - reach for a FIFO queue, or a deque of indices kept in sorted order.
Memory hack Old ones leave by the front door, weak ones get bounced out the back - so whoever stands at the front is always the champion.
Open the Queue & Monotonic Deque guide →Approaches
Brute ForceDP, Scan the Last k Scores
O(n · k)Space O(n)Let dp[i] be the best score that ends on index i.
The previous landing spot is one of the k indices before it, so take
the best of those and add nums[i].
public int maxResult(int[] nums, int k) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; for (int i = 1; i < n; i++) { int best = Integer.MIN_VALUE; for (int j = Math.max(0, i - k); j < i; j++) { best = Math.max(best, dp[j]); } dp[i] = nums[i] + best; } return dp[n - 1]; }
Correct recurrence, but n = k = 105 means 1010 steps.
BetterDP + Max-Heap with Lazy Removal
O(n log n)Space O(n)Keep all earlier (dp, index) pairs in a max-heap. Before using
the top, discard it while its index is outside the window
[i-k, i-1]; stale entries buried deeper can wait until they surface.
public int maxResult(int[] nums, int k) { int n = nums.length; // entries are {dp value, index}, largest dp first PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); heap.offer(new int[]{nums[0], 0}); int cur = nums[0]; for (int i = 1; i < n; i++) { while (heap.peek()[1] < i - k) heap.poll(); // out of reach cur = nums[i] + heap.peek()[0]; heap.offer(new int[]{cur, i}); } return cur; }
Fast enough, but the heap adds a log factor the deque avoids.
OptimalDP + Monotonic Deque
O(n)Space O(n)Store indices in a deque whose dp values decrease from front to back. The front is the window maximum once out-of-range indices are dropped. A new index evicts every back index with a smaller-or-equal dp: it is newer and at least as good, so they can never be chosen again.
public int maxResult(int[] nums, int k) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; Deque<Integer> dq = new ArrayDeque<>(); // indices, dp decreasing dq.offerLast(0); for (int i = 1; i < n; i++) { if (dq.peekFirst() < i - k) dq.pollFirst(); // front fell out of the window dp[i] = nums[i] + dp[dq.peekFirst()]; while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast(); dq.offerLast(i); } return dp[n - 1]; }
Dry runnums = [1,-1,-2,4,-7,3], k = 2
- i=01i f·····dp=1, dq=[0]
- i=11f0i····-1+1=0, dq=[0,1]
- i=21f0-1i···-2+1=-1, dq=[0,1,2]
- i=310f-14i··drop 0; 4+0=4, dq=[3]
- i=410-14f-3i·-7+4=-3, dq=[3,4]
- i=510-14f-37i3+4=7 ✔
Every index enters and leaves the deque once — linear time.
if is enough there.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | DP, Scan the Last k Scores | O(n · k) | O(n) |
| Better | DP + Max-Heap with Lazy Removal | O(n log n) | O(n) |
| Optimal | DP + Monotonic Deque | O(n) | O(n) |
- Greedily jumping to the nearest non-negative value — it can miss a better path.
- Using an O(n·k) loop when k can be as large as n.
- Storing dp values instead of indices in the deque — you can't tell when they expire.
- Write the O(n·k) recurrence first, then say “it's a sliding-window max”.
- Mention the heap as a stepping stone before the deque.
- Point out the score fits in
int: |sum| ≤ 104 · 105.