Jump Game VI: DP with Sliding Window Maximum

You are given a 0-indexed integer array nums and an integer k. You start at index 0 and want to reach index n - 1. In one step, you can jump at most k positions forward. Your score is the sum of all nums[j] for each index j you visit along the way. Return the maximum score you can get.

This is LeetCode 1696: Jump Game VI, a medium problem that sits at the intersection of dynamic programming and sliding window techniques. The naive DP solution is clean but too slow. The trick is recognizing that the inner "take the max over a window" operation is a classic sliding window maximum, which you can solve in amortized O(1) per element with a monotonic deque.

Why this problem matters

Jump Game VI is one of those problems that rewards you for knowing your building blocks. If you recognize the DP recurrence and know how to maintain a sliding window maximum, the solution writes itself. If you do not, you will likely time out with the O(nk) approach.

This combination of DP with a sliding window max appears in many variants. Constrained Subsequence Sum (LeetCode 1425) is nearly identical. Problems involving "pick the best option within the last k choices" all follow the same template. Internalizing this pattern gives you a tool that works across a whole family of problems.

The key insight

Define dp[i] as the maximum score you can achieve arriving at index i. The recurrence is:

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

You always collect nums[i] when you land on index i. The best you can do is arrive from whichever of the previous k indices has the highest DP value.

Computing this naively means scanning back k positions for every index, giving O(nk) time. But the "max over a sliding window of size k" is exactly the sliding window maximum problem. A monotonic deque maintains the maximum value in the window and updates in amortized O(1) per element. That brings the total time down to O(n).

The solution

from collections import deque

def max_result(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])

    for i in range(1, n):
        while dq and dq[0] < i - k:
            dq.popleft()

        dp[i] = dp[dq[0]] + nums[i]

        while dq and dp[i] >= dp[dq[-1]]:
            dq.pop()
        dq.append(i)

    return dp[n - 1]

Here is what each piece does:

1. Initialize: dp[0] = nums[0] because the score at the start is just the first element. The deque starts with index 0.
2. Remove expired entries: Before processing index i, pop any index from the front of the deque that is outside the window (more than k steps back).
3. Compute dp[i]: The front of the deque always holds the index with the largest DP value in the window. So dp[i] = dp[dq[0]] + nums[i].
4. Maintain decreasing order: Before adding i to the deque, pop any indices from the back whose DP values are smaller than or equal to dp[i]. They will never be useful because i is both newer (stays in the window longer) and at least as good.
5. Append: Push i onto the back of the deque.

Visual walkthrough

The optimal path is 0 to 1 to 3 to 5, collecting 1 + (-1) + 4 + 3 = 7. Notice how the deque keeps the window maximum accessible in O(1) at every step. When a new DP value is large enough, it flushes smaller entries from the back because those entries can never beat it.

Complexity analysis

DP + monotonic deque: Each index is pushed onto the deque exactly once and popped at most once (from either end). The total number of deque operations across the entire loop is O(n). Combined with the O(n) loop itself, the time is O(n). Space is O(n) for the DP array and the deque.

Naive DP: For each of the n indices, you scan back up to k positions to find the maximum. In the worst case, this is O(nk). When k is close to n, that becomes O(n^2).

You could also use a max-heap (priority queue) instead of a deque. That gives O(n log n) time because each heap operation is O(log n). The deque approach is better because it achieves O(n) by exploiting the fact that the window slides one position at a time.

The building blocks

1. Sliding window maximum with monotonic deque

The core technique is maintaining the maximum value across a sliding window of size k in amortized O(1) per step. The deque stores indices, and the DP values at those indices are always in strictly decreasing order.

dq = deque()

for i in range(n):
    while dq and dq[0] < i - k:
        dq.popleft()

    window_max = values[dq[0]]

    while dq and values[i] >= values[dq[-1]]:
        dq.pop()
    dq.append(i)

This pattern appears in the classic "Sliding Window Maximum" problem (LeetCode 239) and any problem that needs a running maximum or minimum over a fixed-size window. The key invariant is: the deque front is always the index of the largest value in the current window.

2. DP with window constraint

The DP recurrence dp[i] = nums[i] + max(dp[i-k:i]) is a pattern where each state depends on the best value within a bounded lookback. Without the deque optimization, you would write:

for i in range(1, n):
    dp[i] = nums[i] + max(dp[max(0, i - k):i])

That inner max() call scans up to k elements each time. Recognizing this as a sliding window maximum is the key optimization step. Whenever you see a DP recurrence that takes the max or min over a window of the previous states, reach for the monotonic deque.

Edge cases

Before submitting, make sure your solution handles these:

• Single element nums = [5], k = 1: the answer is 5. You are already at the last index.
• All negative values nums = [-3, -2, -5, -1], k = 2: you still must reach the end. The answer is the least-negative path, which is -3 + (-2) + (-1) = -6.
• k equals n nums = [1, -1, -1, -1, 10], k = 5: you can jump directly from index 0 to any index, so dp[4] = 1 + 10 = 11.
• k equals 1 (forced to visit every index): the answer is sum(nums) because there is no choice in which indices to skip.
• Large k with alternating signs: the deque correctly prunes stale entries so you never pick a value from outside the window.

From understanding to recall

You have seen how the monotonic deque turns an O(nk) DP into an O(n) algorithm. The logic is compact: remove expired entries from the front, read the window max from the front, maintain decreasing order by popping from the back, then append. Four operations per index, each amortized O(1).

But writing it correctly under time pressure is another matter. Which end do you pop expired entries from? Do you use strict or non-strict comparison when popping from the back? Is the initial deque [0] or empty? These details are small but easy to get wrong if you have not practiced.

Spaced repetition is what turns understanding into recall. You practice writing the deque-based DP from scratch at increasing intervals. After a few rounds, the pattern is in your long-term memory. You see "maximize score with bounded jumps" and the code flows without hesitation.

Related posts

• Jump Game - The original reachability problem solved with a greedy scan
• Jump Game II - Minimum number of jumps using BFS-style greedy
• Daily Temperatures - Monotonic stack/deque pattern for next-greater-element problems

CodeBricks breaks Jump Game VI into its sliding-window-maximum and windowed-DP building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the deque logic is automatic. When a bounded-window DP problem shows up in your interview, you do not hesitate. You just write it.