Jump Game VI
You start at the first index of an array and want to reach the last one. From index i you may jump to any index from i + 1 up to i + k, as long as it stays inside the array. Your score is the sum of every value you land on, including the first and the last. Return the largest score you can finish with . The best score for index i is the best score for one of the k indexes behind it, plus the value at i. Checking all k of them is too slow, so keep a deque of indexes whose best scores go downwards from the front . The front is then always the best score you can jump from, and any index with a worse score than the one you just worked out can be thrown away for good.
Constraints
- 1 ≤ nums.length ≤ 105
- -104 ≤ numsi ≤ 104
- 1 ≤ k ≤ nums.length
- You must land on the last index, even if its value is negative
Example
nums = [1, -1, -2, 4, -7, 3], k = 27Explanation Jump from index 0 to 1, then 3, then 5. The values you land on are 1, -1, 4 and 3, which add up to 7.
In plain terms
- Deque
- Short for double ended queue: you can add and remove at both ends. Here you remove stale indexes from the front and weaker indexes from the back.
- Monotonic deque
- A deque kept in a deliberate order. This one holds indexes whose best scores only go down from front to back, so the front is always the largest.
- Best score so far (dp)
- For each index, the highest total you can have when you land on it. Each one is worked out once and then reused.
- Stale index
- An index that is now further back than k steps, so you can no longer jump from it. It is dropped from the front of the deque.
One row of cells is the best score for each index; the frame is the k step reach
The best score at index 0 is just its own value, 1. The deque starts with index 0.
What happens in this step
nums = [1, -1, -2, 4, -7, 3], k = 2 best[0] = 1 deque = [0] You always start on index 0, so nothing has to be decided there. The deque holds candidate indexes to jump from, best score at the front.
Steps to visualize
- Each cell holds the best score for that index, or a dash if it has not been worked out yet.
- The highlight frame spans the indexes you could have jumped from, which is i - k up to i.
- The deque holds the indexes inside that frame worth considering, best score first.
- Before using the front, throw away anything that has fallen out of reach; after filling a cell, throw away any index at the back with a score that is no better.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
The best score at index 0 is just its own value, 1. The deque starts with index 0.
What happens in this step
nums = [1, -1, -2, 4, -7, 3], k = 2 best[0] = 1 deque = [0] You always start on index 0, so nothing has to be decided there. The deque holds candidate indexes to jump from, best score at the front.
Solution
function maxResult(nums, k) {
const dp = new Array(nums.length).fill(0);
const window = [];
dp[0] = nums[0];
window.push(0);
for (let i = 1; i < nums.length; i++) {
while (window.length > 0 && window[0] < i - k) {
window.shift();
}
dp[i] = dp[window[0]] + nums[i];
while (window.length > 0 && dp[window[window.length - 1]] <= dp[i]) {
window.pop();
}
window.push(i);
}
return dp[nums.length - 1];
}- Time
- O(n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [1, -1, -2, 4, -7, 3], k = 2 | 7 | example from the docstring |
nums = [5], k = 1 | 5 | start and finish are the same index, the smallest input |
nums = [1, 2, 3], k = 1 | 6 | every index must be visited when k is 1 |
nums = [-1, -2, -3], k = 1 | -6 | every score is negative and no index can be skipped |
nums = [10, -5, -2, 4, 0, 3], k = 3 | 17 | a larger k lets you jump over the negative run |
nums = [1, -5, -20, 4, -1, 3, -6, -3], k = 2 | 0 | a longer array where the best total lands exactly on zero |