https://leetcode.com/problems/jump-game-vi/
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
- code TLE
class Solution {
public int maxResult(int[] nums, int k) {
int[] dp = new int[nums.length+1];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++){
for (int step = 1; step <= k; step++){
if (i - step >= 0){
dp[i] = Math.max(dp[i], dp[i-step] + nums[i]);
}
}
}
return dp[nums.length-1];
}
}
- code
class Solution {
public int maxResult(int[] nums, int k) {
// index of num, biggest score
Deque<int[]> q = new ArrayDeque<>();
int score = nums[0];
q.offerLast(new int[]{0, nums[0]});
for (int i = 1; i < nums.length; i++){ // not from i = 0
while (q.peekFirst() != null && q.peekFirst()[0] < i - k){
q.pollFirst();
}
score = q.peekFirst()[1] + nums[i];
while (q.peekLast() != null && score >= q.peekLast()[1]){
q.pollLast();
}
q.offerLast(new int[]{i, score});
}
return score;
}
}