Problem Description

You are given an integer array nums and an integer k. Starting at index 0, you can jump at most k steps forward at a time. Each time you land on an index i, you add nums[i] to your score. Your goal is to reach the last index of the array (index n - 1) with the maximum possible score.

• You can only jump forward, and at each step, you may jump to any index j where i < j ≤ i + k.
• You must not reuse elements; each index can only be visited once in your path.
• Return the highest score possible to reach the last index.

Key Constraints:

• There is always at least one valid path to the end.
• All jumps must be within the allowed range (k).

Thought Process

At first glance, the problem looks similar to other "jump game" problems, but with a twist: instead of just checking if you can reach the end, you must maximize your score along the way. The naive approach would be to try every possible path recursively and pick the one with the highest score. However, this is very inefficient because the number of possible paths grows exponentially with the size of the array.

To optimize, we can think in terms of dynamic programming: at each position, what is the best score we could have achieved to get there? This way, we avoid recomputing the same subproblems and only focus on the best possible route to each index.

The challenge then becomes efficiently finding the maximum score among the previous k positions for each step. A brute-force check of the last k positions for every index is too slow for large arrays, so we need a way to quickly find the maximum in a sliding window — this is where a deque (double-ended queue) comes in handy.

Solution Approach

• Dynamic Programming (DP):
  • Define dp[i] as the maximum score to reach index i.
  • For each index i, dp[i] = nums[i] + max(dp[j]) for j in [i-k, i-1].
• Sliding Window Maximum with Deque:
  • To efficiently get the maximum dp value in the last k steps, use a deque to store indices of potential candidates in decreasing order of their dp values.
  • For each index i:
    • Remove indices from the front of the deque if they are out of the window (< i-k).
    • The front of the deque always gives the index with the current maximum dp value in the window.
    • Compute dp[i] = nums[i] + dp[deque[0]].
    • Remove indices from the back of the deque if their dp value is less than or equal to dp[i] (they can't be better for future positions).
    • Add i to the deque.
• Return: The value at dp[n-1] is the answer.

This approach ensures every element is pushed and popped from the deque at most once, giving an efficient solution.

Example Walkthrough

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

• Initialize dp[0] = nums[0] = 1.
• At i = 1: Can come from i = 0. dp[1] = -1 + 1 = 0.
• At i = 2: Can come from i = 0 or i = 1. dp[2] = -2 + max(1, 0) = -1.
• At i = 3: Can come from i = 1 or i = 2. dp[3] = 4 + max(0, -1) = 4.
• At i = 4: Can come from i = 2 or i = 3. dp[4] = -7 + max(-1, 4) = -3.
• At i = 5: Can come from i = 3 or i = 4. dp[5] = 3 + max(4, -3) = 7.

The maximum score to reach the end is 7.

At each step, the deque ensures we always know the best previous position to jump from within the window of k steps.

Time and Space Complexity

• Brute-force: For each index, check all previous k positions, leading to O(nk) time and O(n) space.
• Optimized (Deque): Each index is added and removed from the deque at most once, so the total time is O(n). Space is O(n) for the dp array and the deque.

The optimized approach is much faster and well-suited for large inputs.

Summary

The key to solving Jump Game VI efficiently is to combine dynamic programming with a sliding window maximum. By using a deque, we can always access the best score in the last k steps in constant time, avoiding brute-force checks. This approach is both elegant and efficient, transforming a potentially slow problem into one that runs in linear time.

Code Implementation

from collections import deque

class Solution:
    def maxResult(self, nums, k):
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        dq = deque([0])
        for i in range(1, n):
            # Remove indices out of window
            while dq and dq[0] < i - k:
                dq.popleft()
            dp[i] = nums[i] + dp[dq[0]]
            # Maintain decreasing order in deque
            while dq and dp[i] >= dp[dq[-1]]:
                dq.pop()
            dq.append(i)
        return dp[-1]
      

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        deque<int> dq;
        dq.push_back(0);
        for (int i = 1; i < n; ++i) {
            while (!dq.empty() && dq.front() < i - k)
                dq.pop_front();
            dp[i] = nums[i] + dp[dq.front()];
            while (!dq.empty() && dp[i] >= dp[dq.back()])
                dq.pop_back();
            dq.push_back(i);
        }
        return dp[n - 1];
    }
};
      

import java.util.*;

class Solution {
    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<>();
        dq.addLast(0);
        for (int i = 1; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k) {
                dq.pollFirst();
            }
            dp[i] = nums[i] + dp[dq.peekFirst()];
            while (!dq.isEmpty() && dp[i] >= dp[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.addLast(i);
        }
        return dp[n - 1];
    }
}
      

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxResult = function(nums, k) {
    const n = nums.length;
    const dp = Array(n).fill(0);
    dp[0] = nums[0];
    const dq = [];
    dq.push(0);
    for (let i = 1; i < n; i++) {
        while (dq.length && dq[0] < i - k) {
            dq.shift();
        }
        dp[i] = nums[i] + dp[dq[0]];
        while (dq.length && dp[i] >= dp[dq[dq.length - 1]]) {
            dq.pop();
        }
        dq.push(i);
    }
    return dp[n - 1];
};