Problem statement

You start on index 0 of the integer array nums and want to reach the last index. From index i you may jump forward by 1 to k steps, to any index in [i + 1, min(n - 1, i + k)].

Your score is the sum of nums[j] over every index j you stand on, including the first and the last. Return the maximum score you can achieve.

Example 1

Input: nums = [2,-3,5,-1,-4,6], k = 2
Output: 12
Explanation: Visit indices 0, 2, 3, 5: 2 + 5 - 1 + 6 = 12.

Example 2

Input: nums = [4,-8,-8,-8,1], k = 3
Output: -3
Explanation: Some negative square must be used: 4 - 8 + 1.

Example 3

Input: nums = [7], k = 1
Output: 7

Constraints

• 1 <= nums.length, k <= 10^5
• -10^4 <= nums[i] <= 10^4

Hints for Jump Game VI

1. Hint 1

   Let dp[i] be the best score of a path ending at i. Then dp[i] = nums[i] + max(dp[i - k..i - 1]).

2. Hint 2

   Computing that maximum directly costs O(k) per index. You need the maximum of a sliding window.

3. Hint 3

   Keep a deque of indices whose dp values decrease from front to back; drop indices that left the window from the front and dominated ones from the back.

How to solve Jump Game VI

The DP dp[i] = nums[i] + max(dp[i - k..i - 1]) is a sliding-window maximum over the dp array itself, which a monotonic deque serves in amortised O(1).

Approach

1. Set dp[0] = nums[0] and a deque holding index 0.
2. For each i from 1: pop indices < i - k from the front; the front is now the best predecessor, so dp[i] = dp[front] + nums[i].
3. Pop indices from the back while their dp is <= dp[i], then push i.
4. Return dp[n - 1].

Why it works

The deque always holds, in increasing index order, the indices of the window that could still be a maximum later: an index with a smaller-or-equal dp than a newer index can never win again, because the newer one stays in the window at least as long. So dp values decrease along the deque and its front is the window maximum.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• A greedy 'jump to the next non-negative number' fails when a negative step is unavoidable.
• Expire indices before reading the front: the window is [i - k, i - 1].
• Scores can be negative; never initialise a maximum to 0.

Reference solution

Python

from typing import List
from collections import deque

def maxResult(nums: List[int], k: int) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])
    for i in range(1, n):
        while dq[0] < i - k:
            dq.popleft()
        dp[i] = dp[dq[0]] + nums[i]
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return dp[-1]

Java

public static int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n];
    int[] dq = new int[n];
    int head = 0, tail = 0;
    dp[0] = nums[0];
    dq[tail++] = 0;
    for (int i = 1; i < n; i++) {
        while (dq[head] < i - k) head++;
        dp[i] = dp[dq[head]] + nums[i];
        while (tail > head && dp[dq[tail - 1]] <= dp[i]) tail--;
        dq[tail++] = i;
    }
    return dp[n - 1];
}

C++

int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n), dq(n);
    int head = 0, tail = 0;
    dp[0] = nums[0];
    dq[tail++] = 0;
    for (int i = 1; i < n; i++) {
        while (dq[head] < i - k) head++;
        dp[i] = dp[dq[head]] + nums[i];
        while (tail > head && dp[dq[tail - 1]] <= dp[i]) tail--;
        dq[tail++] = i;
    }
    return dp[n - 1];
}

JavaScript

var maxResult = function(nums, k) {
    var n = nums.length;
    var dp = new Array(n);
    dp[0] = nums[0];
    var dq = new Array(n);
    var head = 0, tail = 0;
    dq[tail++] = 0;
    for (var i = 1; i < n; i++) {
        while (dq[head] < i - k) head++;
        dp[i] = dp[dq[head]] + nums[i];
        while (tail > head && dp[dq[tail - 1]] <= dp[i]) tail--;
        dq[tail++] = i;
    }
    return dp[n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium