#1696

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Jump Game VI

Jump Game VI challenges you to maximize your score while jumping through an array using state transition dynamic programming efficiently.

array dynamic programming queue heap priority queue monotonic queue

Problem Statement

You are given a 0-indexed integer array nums and an integer k. From index 0, you can jump forward at most k steps without leaving the array boundaries. Each jump from index i can reach any index j such that i + 1 <= j <= min(n - 1, i + k).

Your goal is to reach the last index of the array, maximizing your total score. The score is defined as the sum of nums[j] for every index j you visit. Determine the highest score possible when moving optimally from the first to the last index.

Examples

Example 1

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

Output: 7

You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

Example 2

Input: nums = [10,-5,-2,4,0,3], k = 3

Output: 17

You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.

Example 3

Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2

Output: 0

Example details omitted.

Constraints

1 <= nums.length, k <= 105
-104 <= nums[i] <= 104

Solution Approach

Dynamic Programming Setup

Define dp[i] as the maximum score to reach the end starting at index i. The state transition is dp[i] = nums[i] + max(dp[i+1], dp[i+2], ..., dp[i+k]). This captures the score by considering all reachable next steps within k distance.

Monotonic Queue Optimization

Use a monotonic deque to maintain indices of dp values in decreasing order. At each index i, remove indices outside the k-range and use the deque front to find max(dp[j]) efficiently. This reduces time complexity from O(n*k) to O(n).

Implementation Details

Iterate through the array, updating dp values using the deque. Push the current index to the deque while preserving monotonic order. At the end, dp[0] contains the maximum score achievable from start to finish.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The naive approach is O(n*k) due to checking up to k previous dp values per index. Using a monotonic deque reduces this to O(n) time and O(k) space, as each element is pushed and popped at most once.

What Interviewers Usually Probe

Focus on sliding window maximum optimization for dynamic programming.
Expect explanation of deque usage to avoid redundant max calculations.
Be ready to discuss edge cases with negative numbers and small k values.

Common Pitfalls or Variants

Common pitfalls

Using simple nested loops without deque causes timeouts for large arrays.
Forgetting to remove indices outside the k-range from the deque.
Confusing dp[i] as max score from start instead of from current index.

Follow-up variants

Jump Game VI with varying k per index, requiring dynamic window adjustments.
Minimizing the score instead of maximizing, changing deque logic accordingly.
Allowing backward jumps up to k steps, adding bidirectional state management.

FAQ

What is the optimal strategy for Jump Game VI?

Use dynamic programming with a monotonic deque to track the maximum reachable score within k steps, ensuring each dp[i] captures the best subsequence sum.

Why is a monotonic queue necessary in this problem?

It efficiently maintains the maximum dp value within the k-step window, reducing the naive O(n*k) approach to O(n).

How do negative numbers in nums affect the solution?

Negative values reduce the cumulative score, but the deque still correctly identifies the maximum reachable dp value at each step.

Can Jump Game VI be solved without extra space?

In theory yes, but using the monotonic deque simplifies managing the sliding window maximum and ensures O(n) time.

What is the core pattern behind Jump Game VI?

This problem exemplifies state transition dynamic programming combined with sliding window maximum optimization using a monotonic queue.

terminal

Solution

Solution 1: Dynamic Programming + Monotonic Queue Optimization

We define $f[i]$ as the maximum score when reaching index $i$. The value of $f[i]$ can be transferred from $f[j]$, where $j$ satisfies $i - k \leq j \leq i - 1$. Therefore, we can use dynamic programming to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [0] * n
        q = deque([0])
        for i in range(n):
            if i - q[0] > k:
                q.popleft()
            f[i] = nums[i] + f[q[0]]
            while q and f[q[-1]] <= f[i]:
                q.pop()
            q.append(i)
        return f[-1]

Continue Practicing

#1687 delivering boxes from storage to ports #1425 constrained subsequence sum #1438 longest continuous subarray with absolute diff less than or equal to limit