Jump Game VI

MediumProblemExternal linkUpdated Oct 31, 2026

Description

You get an array of integers nums and an integer k. You start on index 0. In one move you can jump forward at most k steps, from index i to any index in [i + 1, min(n - 1, i + k)], without leaving the array. You want to reach the last index, n - 1.

Your score is the sum of nums[j] over every index j you land on, the first and last included. Return the largest score you can get.

Examples

Example 1

Input: nums = [1, -1, -2, 4, -7, 3], k = 2

Output: 7

Explanation: Land on 1, −1, 4 and 3: jumps of 1, 2 and 2, for a total of 7.

Example 2

Input: nums = [10, -5, -2, 4, 0, 3], k = 3

Output: 17

Explanation: Land on 10, 4 and 3: jumps of 3 and 2, for 17.

Example 3

Input: nums = [1, -5, -20, 4, -1, 3, -6, -3], k = 2

Output: 0

Explanation: The best path lands on 1, −5, 4, 3 and −3: 0. Every jump of at most 2 has to step on −5 or −20, and on −6 or −3 near the end.

Constraints

1 ≤ nums.length, k ≤ 10^5
−10^4 ≤ nums[i] ≤ 10^4

Editorial

Brute Force

Intuition

Let dp[i] be the best score of a path that ends on index i. A path that ends on i made its last jump from one of the k indexes before it, so take the best of those and add nums[i]:

dp[i] = nums[i] + max(dp[i - k], …, dp[i - 1])

with dp[0] = nums[0], since every path starts there. Fill dp left to right; the answer is dp[n - 1].

Step-by-Step Explanation

Let's trace nums = [1, -1, -2, 4, -7, 3], k = 2:

dp[0] = 1: every path starts there.
Index 1: the answers in reach are 1; the best is 1, so dp[1] = −1 + 1 = 0.
Index 2: the answers in reach are 1 and 0; the best is 1, so dp[2] = −2 + 1 = −1.
Index 3: the answers in reach are 0 and −1; the best is 0, so dp[3] = 4 + 0 = 4.
Index 4: the answers in reach are −1 and 4; the best is 4, so dp[4] = −7 + 4 = −3.
Index 5: the answers in reach are 4 and −3; the best is 4, so dp[5] = 3 + 4 = 7.

Rescan the Last k Answers — The outlined window is where index i can be reached from.

Algorithm

dp[0] = nums[0].
For i from 1 to n - 1: dp[i] = nums[i] + max(dp[j]) over j from max(0, i - k) to i - 1.
Return dp[n - 1].

Code

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);                   // dp[i]: the best score of a path that ends on i
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            int best = INT_MIN;
            for (int j = max(0, i - k); j < i; j++)   // every index that can jump to i
                best = max(best, dp[j]);
            dp[i] = nums[i] + best;
        }
        return dp[n - 1];
    }
};

class Solution:
    def maxResult(self, nums: list[int], k: int) -> int:
        dp = [0] * len(nums)                 # dp[i]: the best score of a path that ends on i
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            best = max(dp[j] for j in range(max(0, i - k), i))   # every index that can jump to i
            dp[i] = nums[i] + best
        return dp[-1]

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];                    // dp[i]: the best score of a path that ends on i
        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++)   // every index that can jump to i
                best = Math.max(best, dp[j]);
            dp[i] = nums[i] + best;
        }
        return dp[n - 1];
    }
}

var maxResult = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n).fill(0);         // dp[i]: the best score of a path that ends on i
    dp[0] = nums[0];
    for (let i = 1; i < n; i++) {
        let best = -Infinity;
        for (let j = Math.max(0, i - k); j < i; j++)   // every index that can jump to i
            best = Math.max(best, dp[j]);
        dp[i] = nums[i] + best;
    }
    return dp[n - 1];
};

Complexity Analysis

Time Complexity: O(n·k)

Each index scans up to k earlier answers.

Space Complexity: O(n)

The dp array.

Why This Approach Is Not Efficient

With 10^5 values and k = 5 × 10^4, each index scans up to 5 × 10^4 answers: billions of steps, over the time limit in Python and JavaScript. Look at what it scans, though: the window dp[i - k .. i - 1] slides one step to the right for each i. Each step asks for a sliding window's maximum, over the dp values themselves.

A heap of (dp, index) pairs would answer that in O(log n). A monotonic deque answers it in O(1) on average, the same deque that solves Sliding Window Maximum. The one thing to watch is the window's edges: here it's i - k to i - 1, so index i - k is still a legal place to jump from.

Optimal Approach - A Monotonic Deque Over dp

Intuition

Keep a deque of indexes whose dp values fall from front to back. For each i:

If the front is more than k back, < i - k, it can't reach i: pop it.
The front is now the best place to jump from: dp[i] = nums[i] + dp[front].
Pop the back while its dp is ≤ dp[i]: i is later and at least as good, so it beats them for every index still to come. Push i.

Step-by-Step Explanation

Let's trace nums = [1, -1, -2, 4, -7, 3], k = 2:

dp[0] = 1, where every path starts.
dp[1] is −1 + 1 = 0, jumping from index 0.
dp[2] is −2 + 1 = −1, jumping from index 0.
Index 0 is more than 2 back, so it leaves the front. dp[3] is 4 + 0 = 4, jumping from index 1. It knocks −1 and 0 off the back, since a later and better place to jump from beats them.
dp[4] is −7 + 4 = −3, jumping from index 3.
dp[5] is 3 + 4 = 7, jumping from index 3. It knocks −3 and 4 off the back, since a later and better place to jump from beats them.

The Best of the Last k, Kept in Front — The bottom row holds the deque's dp values, falling; its front is the best place to jump from.

Algorithm

Start with an empty deque.
For each i: pop the front if it's < i - k; set dp[i] = nums[i] + dp[front] (or nums[0] for i = 0); pop the back while dp[back] <= dp[i]; push i.
Return dp[n - 1].

Code

JavaScript keeps the deque in an array with a head and a tail index: every index is pushed once, so n slots are enough.

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);                   // dp[i]: the best score of a path that ends on i
        deque<int> dq;                       // indexes, their dp values falling: the front is the best
        for (int i = 0; i < n; i++) {
            if (!dq.empty() && dq.front() < i - k)
                dq.pop_front();              // more than k back: too far to jump from
            dp[i] = nums[i] + (dq.empty() ? 0 : dp[dq.front()]);
            while (!dq.empty() && dp[dq.back()] <= dp[i])
                dq.pop_back();
            dq.push_back(i);
        }
        return dp[n - 1];
    }
};

from collections import deque

class Solution:
    def maxResult(self, nums: list[int], k: int) -> int:
        dp = [0] * len(nums)                 # dp[i]: the best score of a path that ends on i
        dq = deque()                         # indexes, their dp values falling: dq[0] is the best
        for i, x in enumerate(nums):
            if dq and dq[0] < i - k:
                dq.popleft()                 # more than k back: too far to jump from
            dp[i] = x + (dp[dq[0]] if dq else 0)
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)
        return dp[-1]

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];                    // dp[i]: the best score of a path that ends on i
        Deque<Integer> dq = new ArrayDeque<>();   // indexes, their dp values falling: the front is the best
        for (int i = 0; i < n; i++) {
            if (!dq.isEmpty() && dq.peekFirst() < i - k)
                dq.pollFirst();                   // more than k back: too far to jump from
            dp[i] = nums[i] + (dq.isEmpty() ? 0 : dp[dq.peekFirst()]);
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i])
                dq.pollLast();
            dq.offerLast(i);
        }
        return dp[n - 1];
    }
}

var maxResult = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n).fill(0);         // dp[i]: the best score of a path that ends on i
    const dq = new Int32Array(n);            // indexes, their dp values falling: dq[head] is the best
    let head = 0, tail = 0;
    for (let i = 0; i < n; i++) {
        if (tail > head && dq[head] < i - k)
            head++;                          // more than k back: too far to jump from
        dp[i] = nums[i] + (tail > head ? dp[dq[head]] : 0);
        while (tail > head && dp[dq[tail - 1]] <= dp[i])
            tail--;
        dq[tail++] = i;
    }
    return dp[n - 1];
};

Complexity Analysis

Time Complexity: O(n)

Each index is pushed once and popped at most once.

Space Complexity: O(n)

The dp array and the deque.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Dropping the jump of exactly k. if dq and dq[0] <= i - k:

On nums = [1, -1, -2, 4, -7, 3], k = 2 it returns -2; the answer is 7. dp[i] may come from any of i - k to i - 1, so index i - k is still a legal place to jump from. <= i - k is the window maximum's test, and here it drops a jump of exactly k. Use < i - k.

Letting the path start fresh. dp[i] = x + max(0, dp[dq[0]] if dq else 0)

On nums = [-5, 1], k = 1 it returns 1; the answer is -4. Every path starts at index 0, so a negative start can't be skipped. Taking max(0, best) is Constrained Subsequence Sum's rule, where a subsequence may start fresh; here it isn't allowed.

Jumping to the biggest value in reach. i = max(reach, key=lambda j: (nums[j], j))

On nums = [1, 2, 3, 4], k = 3 it returns 5; the answer is 10. Taking the best value within k steps each time can jump over values worth collecting, or walk into large negatives that a different jump would avoid. Each choice has to weigh every path after it, which is what dp does.

Where This Pattern Is Taught

This problem practises a monotonic deque over earlier answers. It's taught in Monotonic Deque: the Window's Maximum, which runs this recurrence and the off-by-one in its expiry test. Constrained Subsequence Sum is the same recurrence with a fresh start allowed.