AlgoMaster Logo

Jump Game VI

Last Updated: March 29, 2026

medium
5 min read

Understanding the Problem

We start at index 0 and must reach index n-1. From any position i, we can jump forward by 1 to k positions. Every index we land on adds nums[j] to our score, and we want to maximize that total score.

A couple of things make this interesting. First, we must visit both the first and last index, there's no choice about that. Second, the values can be negative, so we might be forced to step through some bad indices if the jump distance k doesn't let us skip over them. Third, this isn't about choosing whether to include elements (like a subsequence problem), it's about choosing a path from start to end where consecutive steps are at most k apart.

The key observation: if we define dp[i] as the maximum score to reach index i starting from index 0, then dp[i] = nums[i] + max(dp[j]) for j in [max(0, i-k), i-1]. We must include nums[i] (we're landing on it), and we pick the best preceding index within jump range. The answer is dp[n-1].

Key Constraints:

  • 1 <= nums.length <= 10^5 -- With n up to 100,000, an O(n*k) brute force could be O(n^2) in the worst case (when k is close to n). We need O(n log n) or O(n).
  • -10^4 <= nums[i] <= 10^4 -- Negative values mean we can't simply skip indices freely. Sometimes we're forced through negatives when k is small.
  • 1 <= k <= nums.length -- When k = n, we can jump from index 0 directly to n-1, so the answer is just nums[0] + nums[n-1]. When k = 1, we must visit every index.

Approach 1: Dynamic Programming (Brute Force)

Intuition

The most natural approach is to define dp[i] as the maximum score to reach index i from index 0. For each index, we look back at the previous k positions and pick the one with the highest dp value. Since we must land on index i, we add nums[i] to whatever the best preceding score was.

The recurrence is: dp[i] = nums[i] + max(dp[j]) for j in [max(0, i-k), i-1].

The base case is dp[0] = nums[0] since we start at index 0. The answer is dp[n-1] since we must reach the last index.

Algorithm

  1. Create a dp array of size n. Set dp[0] = nums[0].
  2. For each index i from 1 to n-1, look back at all dp values in the range [max(0, i-k), i-1].
  3. Find the maximum among those dp values.
  4. Set dp[i] = nums[i] + maxPrev.
  5. Return dp[n-1].

Example Walkthrough

1Initialize: dp[0] = nums[0] = 1
0
1
dp[0]=1
1
0
2
0
3
0
4
0
5
0
1/7

Code

This approach works but the inner loop rescans almost the same window at every step. What if we maintained a data structure that tracks the window maximum as it slides forward?

Approach 2: DP with Heap (Priority Queue)

Intuition

Instead of rescanning the window from scratch at each step, we can use a max-heap to keep track of dp values within the window. The heap gives us the maximum in O(1) via a peek, and insertions cost O(log n).

There's a catch though. When we peek at the heap's maximum, that entry might belong to an index that's already fallen out of our window. So we store both the dp value and its index in the heap, and lazily pop stale entries from the top whenever we need the current maximum.

Algorithm

  1. Create a max-heap. Set dp[0] = nums[0] and push (dp[0], 0) into the heap.
  2. For each index i from 1 to n-1:
    • While the top of the heap has an index less than i - k, pop it (it's outside the window).
    • The heap's top now gives the best dp value within jump range.
    • Set dp[i] = nums[i] + heap_top_value.
    • Push (dp[i], i) into the heap.
  3. Return dp[n-1].

Example Walkthrough

1Initialize: dp[0] = nums[0] = 1, push (1, 0) to heap
0
1
dp[0]=1
1
0
2
0
3
0
4
0
5
0
1/7

Code

The heap maintains full sorted order, but we only need the maximum. What if we kept only the elements that could potentially be the window maximum?

Approach 3: DP with Monotonic Deque (Optimal)

Intuition

This is the classic "sliding window maximum" technique applied to a DP recurrence. Instead of a full heap, we maintain a monotonic decreasing deque of indices. The front of the deque always holds the index with the largest dp value in the current window.

Why does a decreasing deque work? Consider two indices i < j where dp[i] <= dp[j]. Index i will never be the best choice for any future position. It's older (will fall out of the window sooner) and has a smaller or equal dp value. So it's completely dominated by j, and we can safely discard it. By removing all such dominated entries from the back of the deque before inserting a new element, we maintain a strictly decreasing sequence of dp values.

Algorithm

  1. Create a deque that stores indices. Initialize with index 0, set dp[0] = nums[0].
  2. For each index i from 1 to n-1:
    • Remove indices from the front of the deque that are outside the window (index < i - k).
    • The front of the deque gives the index with the maximum dp value in the window.
    • Set dp[i] = nums[i] + dp[deque.front()].
    • Before pushing i onto the back, remove all indices from the back whose dp values are less than or equal to dp[i] (they're dominated and will never be needed).
    • Push i onto the back of the deque.
  3. Return dp[n-1].

Example Walkthrough

1Initialize: dp[0] = nums[0] = 1, deque = [0]
0
1
dp[0]=1
1
0
2
0
3
0
4
0
5
0
1/7

Code