Jump Game VI
MedPrompt
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] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a straightforward dynamic programming solution. We define dp[i] as the maximum score achievable to reach index i. To compute dp[i], we need to find the maximum score among all possible previous indices j from which we can jump to i. These indices j are in the range [i - k, i - 1]. The recurrence relation is dp[i] = nums[i] + max(dp[j]) for j in [max(0, i - k), i - 1]. We build up the dp array from the beginning to the end.
Algorithm
- Create a DP array
dpof sizen, wherenis the length ofnums. - Initialize
dp[0] = nums[0], as the score to reach the first index is just its value. - Iterate with a loop from
i = 1ton - 1. - Inside this loop, create another loop to find the maximum score among the previous
kreachable indices. Let this bemax_prev. The inner loop iterates fromj = 1tok(as long asi - jis a valid index). - Update
dp[i] = nums[i] + max_prev. - After the outer loop finishes,
dp[n - 1]will hold the maximum score to reach the last index.
Walkthrough
We can solve this problem using dynamic programming. Let's define dp[i] as the maximum score to reach index i. Our goal is to find dp[n-1].
Base Case:
The base case is dp[0] = nums[0], because we start at index 0 and its score is included.
Recurrence Relation:
For any index i > 0, we can reach it from any index j such that i - k <= j < i. To maximize the score at i, we must have come from the previous index j that had the maximum score. Therefore, the score at i is nums[i] plus the maximum score in the window dp[i-k...i-1].
dp[i] = nums[i] + max(dp[i-1], dp[i-2], ..., dp[i-k])
We can implement this by iterating from i = 1 to n-1 and, for each i, iterating again through the last k indices to find the maximum dp value.
class Solution { public int maxResult(int[] nums, int k) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; for (int i = 1; i < n; i++) { int maxPrev = Integer.MIN_VALUE; for (int j = 1; j <= k && i - j >= 0; j++) { maxPrev = Math.max(maxPrev, dp[i - j]); } dp[i] = nums[i] + maxPrev; } return dp[n - 1]; }}Complexity
Time
O(N * K), where N is the number of elements in `nums`. For each element `i`, we look back at `k` previous elements.
Space
O(N) to store the `dp` array.
Trade-offs
Pros
Simple to understand and implement.
It correctly formulates the problem as a dynamic programming recurrence.
Cons
The time complexity of O(N * K) is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
Solutions
Solution
class Solution {public int maxResult(int[] nums, int k) { int n = nums.length; int[] f = new int[n]; Deque<Integer> q = new ArrayDeque<>(); q.offer(0); for (int i = 0; i < n; ++i) { if (i - q.peekFirst() > k) { q.pollFirst(); } f[i] = nums[i] + f[q.peekFirst()]; while (!q.isEmpty() && f[q.peekLast()] <= f[i]) { q.pollLast(); } q.offerLast(i); } return f[n - 1]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.