Jump Game VI — DP with Monotonic Deque Sliding Window Max [LeetCode 1696]

Problem Statement#

LeetCode 1696 — Jump Game VI (Medium)

You are given a 0-indexed integer array nums and an integer k. You are initially at index 0. In one move, you can jump at most k steps forward without going out of bounds. You want to reach the last index. Your score is the sum of all values of the indices you visited. Return the maximum score you can get.

Constraints:

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

Example 1:

Input:  nums = [1, -1, -2, 4, -7, 3], k = 2
Output: 7
Explanation: Jump to indices 0→1→3→5 with scores 1+(-1)+4+3=7.
             This beats 0→2→3→5: 1+(-2)+4+3=6.

Example 2:

Input:  nums = [10, -5, -2, 4, 0, 3], k = 3
Output: 17
Explanation: Jump 0→3→5: 10+4+3=17.

Example 3:

Input:  nums = [1, -5, -20, 4, -1, 3, -6, -3], k = 2
Output: 0
Explanation: Jump 0→3→4→5: 1+4+(-1)+3=7? No, best is 0→1→3→4→5: 1+(-5)+4+(-1)+3=2.
             Let me recalculate: best path gives 0.

Why This Problem Matters#

Jump Game VI is the bridge between dynamic programming and monotonic deque (sliding window maximum) — two important patterns that are powerful individually but even more powerful combined. Amazon and Google frequently ask this problem because it requires recognising that a straightforward O(n*k) DP can be optimised to O(n) using a deque, and implementing that optimisation cleanly under interview pressure.

The sliding window maximum pattern is itself used in dozens of problems: maximum in a sliding window (LeetCode 239), constrained subsequence sum (LeetCode 1425), and maximum score from grid (LeetCode 1301). Mastering it here gives you the key subroutine for all these problems.

The problem is also a natural evolution of the Jump Game series (LeetCode 55, 45). It adds a score dimension and requires understanding that dynamic programming with range maximums is the right framework, then pushes you to optimise with the deque.

In practice, this models scenarios like maximising profit on a journey where you can choose to stop at intermediate points (within k steps), or maximising data collection in a pipeline where you can skip at most k-1 stages between readings.

The Core Insight#

DP recurrence: Let dp[i] = maximum score to reach index i. Then:

• dp[0] = nums[0]
• dp[i] = nums[i] + max(dp[i-k], dp[i-k+1], ..., dp[i-1])

This is: the maximum DP value from the last k positions, plus the current cell's value.

Naive DP: O(n * k) — for each position, scan back k positions.

Optimisation: The recurrence needs the maximum of a sliding window of size k over the dp array. This is the classic "sliding window maximum" problem, solvable in O(1) per step using a monotonic deque that maintains indices of potential maximum dp values.

The deque stores indices in decreasing order of their dp values (front has the maximum). At each step:

1. Remove indices from the front that are outside the window (more than k steps back).
2. The front of the deque gives the maximum dp value in the window.
3. Compute dp[i] = nums[i] + dp[deque.front()].
4. Remove indices from the back whose dp values are less than dp[i] (they can never be maximum for future positions).
5. Append i.

Visual Dry Run#

nums = [1, -1, -2, 4, -7, 3], k = 2
dp = [1, -1, -2, 4, -7, 3] (initialise as copy of nums)
deque = [0]  (start with index 0)
 
i=1: remove front if outside window: 0 >= 1-2=-1, keep
     dp[1] = nums[1] + dp[deque[0]] = -1 + dp[0] = -1 + 1 = 0
     remove back while dp[back] <= dp[1]=0: dp[0]=1 > 0, no removal
     push 1 → deque=[0,1]
 
i=2: remove front if outside: 0 >= 2-2=0, keep
     dp[2] = nums[2] + dp[0] = -2 + 1 = -1
     remove back while dp[back] <= -1: dp[1]=0 > -1, no removal
     push 2 → deque=[0,1,2]
 
i=3: remove front if outside: 0 < 3-2=1, pop 0 → deque=[1,2]
     dp[3] = nums[3] + dp[1] = 4 + 0 = 4
     remove back while dp[back] <= 4: dp[2]=-1<=4 pop, dp[1]=0<=4 pop
     push 3 → deque=[3]
 
i=4: remove front if outside: 3 >= 4-2=2, keep
     dp[4] = nums[4] + dp[3] = -7 + 4 = -3
     dp[3]=4 > -3, no back removal; push 4 → deque=[3,4]
 
i=5: remove front if outside: 3 >= 5-2=3, keep
     dp[5] = nums[5] + dp[3] = 3 + 4 = 7
     remove back while <= 7: dp[4]=-3<=7 pop, dp[3]=4<=7 pop; push 5 → deque=[5]
 
Answer = dp[5] = 7  ✓

DP values at each step:

Solution (Optimal)#

from collections import deque
 
class Solution:
    def maxResult(self, nums: list[int], k: int) -> int:
        n = len(nums)
        dp = nums[:]  # dp[i] = max score to reach index i
        dq = deque([0])  # monotonic deque of indices, front is max dp
 
        for i in range(1, n):
            # Remove indices outside the window of size k
            while dq and dq[0] < i - k:
                dq.popleft()
 
            # dp[i] = nums[i] + best dp in window [i-k, i-1]
            dp[i] += dp[dq[0]]
 
            # Maintain decreasing order: remove indices with dp <= dp[i]
            # (they can never be the maximum for future positions)
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
 
            dq.append(i)
 
        return dp[-1]

var maxResult = function(nums, k) {
    const n = nums.length;
    const dp = [...nums]; // dp[i] = max score to reach index i
    const dq = [0];       // monotonic deque, front has index of max dp
 
    for (let i = 1; i < n; i++) {
        // Remove indices that are outside the sliding window
        while (dq.length > 0 && dq[0] < i - k) {
            dq.shift();
        }
 
        // dp[i] = nums[i] + max(dp[i-k..i-1]) = nums[i] + dp[dq[0]]
        dp[i] += dp[dq[0]];
 
        // Maintain decreasing dp values in deque
        while (dq.length > 0 && dp[dq[dq.length - 1]] <= dp[i]) {
            dq.pop();
        }
 
        dq.push(i);
    }
 
    return dp[n - 1];
};

Complexity Analysis:

Common Mistakes#

• Using a sorted structure instead of a deque. A sorted set or heap gives O(log k) per operation. The deque achieves O(1) amortised — use the deque.
• Not removing expired indices from the front. The deque front must always be within the window [i-k, i-1]. Not pruning stale indices gives wrong maximums.
• Incorrect deque order. The deque must maintain decreasing dp values (not decreasing indices). The front is the maximum dp, the back is the most recently added minimum.
• Using < vs <= for deque pruning. When dp[dq[-1]] <= dp[i], pop — because dq[-1] can never be the maximum for any future window position (dp[i] is both larger and more recent). Using strict < leaves equal elements that clutter the deque (though technically correct, it is cleaner with <=).
• Initialising dp as [0]*n instead of nums[:]. The score at each index starts with nums[i] itself (you must step on it), so initialise dp[i] = nums[i].

Follow-up Questions#

Q: What if k = 1 (must jump exactly one step at a time)? Then dp[i] = nums[i] + dp[i-1]. No deque needed — just a running sum.

Q: What if k = n (can jump anywhere from any position)? Then dp[i] = nums[i] + max(dp[0], ..., dp[i-1]). Maintain a running maximum instead of a deque.

Q: What if we want to minimise the score instead of maximise? Change the deque to maintain increasing dp values (monotonic increasing deque). The front holds the minimum dp in the window.

Q: How does the monotonic deque differ from a priority queue (heap) here? Both give the window maximum, but the deque is O(1) amortised per operation while a heap is O(log k). The deque exploits the FIFO structure of the sliding window to avoid re-heapifying.

Q: What if nums can contain zeros and we want to count the number of maximum-score paths? Add a separate count array alongside dp. When dp[i] = nums[i] + dp[dq[0]], set count[i] based on how many deque entries achieve the maximum dp value.

Q: Is there a greedy approach that avoids DP? No simple greedy works here because the local maximum in the window may not lead to the global maximum score. DP is necessary.

Related Problems#

• LeetCode 239 — Sliding Window Maximum: Pure sliding window max — this problem's core subroutine.
• LeetCode 1425 — Constrained Subsequence Sum: DP + sliding window max — identical structure, different constraint.
• LeetCode 55 — Jump Game: Can you reach the end — greedy range extension, no score.
• LeetCode 45 — Jump Game II: Minimum jumps to end — greedy BFS layer expansion.
• LeetCode 1306 — Jump Game III: Bidirectional jumps — BFS reachability.
• LeetCode 1871 — Jump Game VII: Jump with forbidden positions — BFS + prefix sums.

Interview Tips#

• Start by writing the O(n*k) DP recurrence on the board, then announce you will optimise the inner max with a monotonic deque.
• Trace the deque step-by-step on a small example to convince the interviewer your invariant holds.
• Mention that this is the same trick used by sliding-window maximum (LeetCode 239).

Key Takeaways#

• Define dp[i] = nums[i] + max(dp[i-k..i-1]) and recognise the inner max is a sliding window maximum.
• Use a monotonic decreasing deque of indices to obtain the window max in amortised O(1) per step.
• Each index enters and leaves the deque at most once, giving an overall O(n) runtime.
• Always pop expired indices from the front before reading the maximum.
• Initialise dp[i] = nums[i] because every visited index contributes its own value.
• The same DP-plus-deque pattern solves Constrained Subsequence Sum (LeetCode 1425) and similar bounded-DP problems.
• For minimisation variants, flip to a monotonic increasing deque holding the window minimum.