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] <= 104This 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.
JavaScript
Java
C#
C
C++
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.
JavaScript
Java
C#
C
C++
Time Complexity: O(n log k) due to heap operations. Space Complexity: O(k), maintaining up to k elements in the heap.
| 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. |
Leetcode 1696. Jump Game VI [Monotone Queue] • Fraz • 11,748 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