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 outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.
You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.
Return the maximum score you can get.
Example 1:
Input: nums = [1,-1,-2,4,-7,3], k = 2 Output: 7 Explanation: 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 Explanation: 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
Constraints:
1 <= nums.length, k <= 105-104 <= nums[i] <= 104Problem Overview: You are given an integer array nums and an integer k. Starting at index 0, you can jump forward at most k positions each move. The goal is to reach the last index while maximizing the total score, where the score is the sum of visited elements.
The challenge is deciding which of the last k positions provides the best previous score before jumping to the current index. This naturally leads to a dynamic programming formulation.
Approach 1: Dynamic Programming (Brute Force Window) (Time: O(nk), Space: O(n))
Define dp[i] as the maximum score you can achieve when landing on index i. For each position, check all reachable previous indices from i-k to i-1 and take the maximum score among them. Then compute dp[i] = nums[i] + max(dp[j]). This works but becomes slow when k is large because every index scans up to k previous states. The approach demonstrates the correct recurrence but does unnecessary repeated work.
Approach 2: Dynamic Programming with Priority Queue (Max-Heap) (Time: O(n log k), Space: O(n))
Instead of scanning the previous k values each time, maintain the best candidate in a heap (priority queue). Store pairs of (dp value, index) in a max-heap. Before computing dp[i], remove elements whose indices fall outside the k-window. The top of the heap always gives the maximum score among the last k positions, allowing dp[i] to be computed in constant time after heap maintenance. Each insertion and removal costs O(log k), which reduces the overall runtime significantly.
Approach 3: Dynamic Programming with Monotonic Deque (Optimal) (Time: O(n), Space: O(n))
The heap approach still performs log k operations. A faster method uses a monotonic queue. Maintain a deque of indices where their dp values are in decreasing order. The front of the deque always holds the index with the best score within the last k steps. When computing dp[i], remove indices from the front if they fall outside the window. Then calculate dp[i] = nums[i] + dp[deque[0]]. Before inserting i, pop elements from the back while their dp values are smaller than dp[i]. This keeps the deque monotonic and ensures each index is inserted and removed at most once.
This sliding-window optimization turns the problem into a linear scan with constant-time updates, making it the most efficient solution. The technique is closely related to problems that combine array traversal with window-based maximum queries.
Recommended for interviews: Interviewers expect the monotonic deque solution with O(n) time complexity. Starting with the basic dynamic programming recurrence shows you understand the state transition. Improving it with a heap demonstrates optimization thinking. Implementing the monotonic queue shows strong mastery of sliding window and DP optimization techniques.
This approach employs dynamic programming in combination with a deque to keep track of the best scores possible when jumping to each index within constraints. By using a decreasing deque, we efficiently maintain the maximum score in a window of size k.
We initialize a deque and iterate over the array. For each index, we ensure that the deque only contains valid indices. We update the current index with the maximum score that can be achieved from the deque front, then maintain a decreasing order in the deque by popping elements smaller than the current score.
Time Complexity: O(n), because each element is inserted and removed from the deque at most once. Space Complexity: O(k), to store the window of indices in the deque.
This approach involves using a dynamic programming solution where we keep track of the best scores using a max-heap (priority queue). By pushing elements onto the heap, we ensure that the maximum score is always accessible, facilitating quick updates for each step in our process.
The solution employs a max-heap by negating values, allowing for priority queue operations to keep track of scores efficiently. The negation allows us to use Python's min-heap to act as a max-heap.
Time Complexity: O(n log k) due to heap operations. Space Complexity: O(k), maintaining up to k elements in the heap.
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.
The state transition equation is:
$
f[i] = max_{j \in [i - k, i - 1]} f[j] + nums[i]
We can use a monotonic queue to optimize the state transition equation. Specifically, we maintain a monotonically decreasing queue, which stores the index j, and the f[j] values corresponding to the indices in the queue are monotonically decreasing. When performing state transition, we only need to take out the index j at the front of the queue to get the maximum value of f[j], and then update the value of f[i] to f[j] + nums[i].
The time complexity is O(n), and the space complexity is O(n). Here, n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Deque Optimization | Time Complexity: O(n), because each element is inserted and removed from the deque at most once. Space Complexity: O(k), to store the window of indices in the deque. |
| Dynamic Programming with Priority Queue (Max-Heap) Optimization | Time Complexity: O(n log k) due to heap operations. Space Complexity: O(k), maintaining up to k elements in the heap. |
| Dynamic Programming + Monotonic Queue Optimization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Brute Force Window) | O(nk) | O(n) | Useful for understanding the DP recurrence or when k is very small |
| DP with Max-Heap (Priority Queue) | O(n log k) | O(n) | Good balance between clarity and performance when heap structures are comfortable |
| DP with Monotonic Deque | O(n) | O(n) | Optimal solution for large inputs and typical interview expectation |
Leetcode 1696. Jump Game VI [Monotone Queue] • Fraz • 13,144 views views
Watch 9 more video solutions →Practice Jump Game VI with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor