Skip to main content

1696 - Jump Game VI

Difficulty: Medium | Pattern: DP + Monotonic Deque | Company tags: Amazon, Google, Bloomberg

Problem Statement​

You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going out-of-bounds of the array. You want to reach the last index of the array.

Your score is the sum of all nums[j] for each index j you visited in the path from 0 to n-1.

Return the maximum score you can get.

Example 1:

Input: nums = [1,-1,-2,4,-7,3], k = 2
Output: 7
Explanation: Jump: 0→3→5: 1+4+3 = 7

Example 2:

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

Approach: DP + Monotonic Deque — O(n)​

Key insight: Define dp[i] = max score to reach index i. The transition is: dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]).

A brute force would check k values for each i → O(nk). Use a monotonic deque (decreasing) to get the window maximum in O(1) amortized.

from collections import deque

def maxResult(nums: list[int], k: int) -> int:
    n = len(nums)
    dp = [float('-inf')] * n
    dp[0] = nums[0]
    
    dq = deque([0])  # indices, decreasing dp values
    
    for i in range(1, n):
        # Remove indices outside window
        while dq and dq[0] < i - k:
            dq.popleft()
        
        dp[i] = nums[i] + dp[dq[0]]
        
        # Maintain decreasing order
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    
    return dp[n - 1]

Algorithm Flow​

Dry Run​

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

inums[i]deque front dpdp[i]deque after
01—1[0]
1-1dp[0]=10[0,1] (dp[0]=1>dp[1]=0)
2-2dp[0]=1-1[0] (pop 1 since dp[1]=0 but... dp[1]=0 >= dp[2]=-1, keep) → [0,1,2]?

Let's trace more carefully. dq stores indices with decreasing dp.

After i=0: dq=[0], dp=[1,-inf,-inf,-inf,-inf,-inf] i=1: front=0, dp[0]=1; dp[1]=-1+1=0; pop back while dp[-1] lte 0: dp[0]=1>0 no pop → dq=[0,1] i=2: front=0 (0 gte 2-2=0 ok); dp[2]=-2+1=-1; pop back while dp[-1] lte -1: dp[1]=0>-1 no pop → dq=[0,1,2] i=3: front=0 but 0 lt 3-2=1 → pop 0; front=1; dp[3]=4+0=4; pop back while dp[-1] lte 4: dp[2]=-1 lte 4 pop, dp[1]=0 lte 4 pop → dq=[3] i=4: front=3 (3 gte 4-2=2 ok); dp[4]=-7+4=-3; dp[3]=4>-3 no pop → dq=[3,4] i=5: front=3 (3 gte 5-2=3 ok); dp[5]=3+4=7; pop back while dp[-1] lte 7: dp[4]=-3 lte 7 pop → dq=[3,5]

dp[5]=7 → 7 ✓

Complexity​

  • Time: O(n) — each index added/removed from deque once
  • Space: O(n) for dp + O(k) for deque

Key Terms​

TermDefinition
Dynamic programmingdp[i] stores the best score achievable to reach index i, built from smaller subproblems.
Monotonic dequeA deque kept in decreasing order of dp values so the front is always the window maximum.
Sliding window maximumThe classic technique of maintaining max of the last k elements in O(1) amortized per step.
Amortized analysisEach index is pushed and popped from the deque at most once, bounding total deque work to O(n).

FAQ​

  1. Why not just use a max-heap for the window maximum? A heap would need O(log n) per operation and lazy deletion for out-of-window elements; the monotonic deque gives O(1) amortized with simpler invariants.
  2. What if k >= n? The window always covers all previous indices, so dp[i] is nums[i] + max(dp[0..i-1]), and the deque still works correctly since it just never evicts from the front.
  3. What if all elements are negative? The algorithm still works — dp values propagate the least negative path since we always take the max in the window.
  4. Can this be solved with plain DP without a deque? Yes, in O(nk), which times out for large n and k; the deque is what reduces it to O(n).
  5. How would this change for "minimum score" instead of maximum? Flip the deque to be increasing instead of decreasing, so the front always holds the minimum dp value in the window.

Quick Revision​

  • Pattern: DP where the transition needs a sliding window maximum.
  • dp[i] = nums[i] + max(dp[i-k..i-1]).
  • Naive max lookup is O(k) per step → O(nk) total; use a monotonic deque to get O(1) amortized.
  • Deque stores indices, kept in decreasing order of dp value.
  • Before reading front: evict indices that fell outside [i-k, i-1].
  • After computing dp[i]: pop back while back's dp ≤ dp[i], then push i.
  • Answer is dp[n-1].
  • Time O(n), space O(n) for dp plus O(k) for the deque.
  • Same deque trick as LeetCode 239 (Sliding Window Maximum).
  • Sliding window maximum pattern: LeetCode 239 (Sliding Window Maximum) — the deque mechanics are identical.
  • 1043-PartitionArrayForMaximumSum.md — another DP-over-window problem.
  • 918-MaximumSumCircularSubarray.md — shares the "max score over positions" DP flavor.