Jump Game VI
Problem
You stand on index 0 of an integer array nums and want to reach the last index. From index i you may hop forward to any index from i+1 up to min(n−1, i+k). Every index you land on (including index 0) adds nums[index] to your score — values can be negative, so greedy hopping can hurt.
Return the maximum total score with which you can reach index n−1.
nums = [1,-1,-2,4,-7,3], k = 27def max_result(nums, k):
from collections import deque
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dq = deque([0]) # indices; dp values decreasing
for i in range(1, n):
while dq[0] < i - k: # front fell out of the window
dq.popleft()
dp[i] = nums[i] + dp[dq[0]]
while dq and dp[dq[-1]] <= dp[i]:
dq.pop() # smaller scores can never win
dq.append(i)
return dp[n - 1]function maxResult(nums, k) {
const n = nums.length;
const dp = new Array(n).fill(0);
dp[0] = nums[0];
const dq = [0]; // indices; dp values decreasing
for (let i = 1; i < n; i++) {
while (dq[0] < i - k) dq.shift(); // front fell out of the window
dp[i] = nums[i] + dp[dq[0]];
while (dq.length && dp[dq[dq.length - 1]] <= dp[i]) dq.pop();
dq.push(i);
}
return dp[n - 1];
}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.addLast(0);
for (int i = 1; i < n; i++) {
while (dq.peekFirst() < i - k) dq.pollFirst(); // out of window
dp[i] = nums[i] + dp[dq.peekFirst()];
while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) dq.pollLast();
dq.addLast(i);
}
return dp[n - 1];
}int maxResult(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = nums[0];
deque<int> dq{0}; // indices; dp values decreasing
for (int i = 1; i < n; i++) {
while (dq.front() < i - k) dq.pop_front(); // out of window
dp[i] = nums[i] + dp[dq.front()];
while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
dq.push_back(i);
}
return dp[n - 1];
}Explanation
Define dp[i] = the maximum score with which you can stand on index i. Since the last hop into i came from one of the previous k indices, dp[i] = nums[i] + max(dp[i−k..i−1]). Computed naively that max costs O(k) per index, O(n·k) overall — too slow when both are 10⁵.
The fix is to notice that max(dp[i−k..i−1]) is a sliding-window maximum, which a monotonic deque answers in O(1). The deque stores indices whose dp values are strictly decreasing from front to back, so the front is always the best score currently inside the window.
For each i we do three things. First, if the front index is older than i−k it has slid out of the window, so we pop it from the front. Second, we read the answer off the front: dp[i] = nums[i] + dp[front]. Third, we pop every back index whose dp is ≤ dp[i] — index i is both newer (stays in the window longer) and at least as good, so those entries can never be the maximum again — and push i.
Walking the default example nums = [1,-1,-2,4,-7,3], k = 2: dp starts [1]. dp[1] = −1+1 = 0, dp[2] = −2+1 = −1 (the front, index 0, still wins). At i = 3 index 0 expires, the front gives dp[3] = 4+0 = 4, and indices 2 and 1 get popped because 4 beats them. dp[4] = −7+4 = −3, and finally dp[5] = 3+4 = 7 — the answer.
Every index is pushed onto the deque exactly once and popped at most once (from front or back), so all the deque work is O(n) amortized. Total time O(n), with O(n) space for the dp array and deque. (Space can be squeezed to O(k) by storing scores in the deque instead of a full dp array.)