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] <= 104struct Solution;
use std::collections::VecDeque;
impl Solution {
fn max_result(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let k = k as usize;
let mut queue: VecDeque<(usize, i32)> = VecDeque::new();
queue.push_back((0, nums[0]));
for i in 1..n {
while let Some((j, _)) = queue.front() {
if j + k < i {
queue.pop_front();
} else {
break;
}
}
let max = queue.front().as_ref().unwrap().1 + nums[i];
while let Some(&(_, sum)) = queue.back() {
if sum < max {
queue.pop_back();
} else {
break;
}
}
queue.push_back((i, max));
}
queue.back().as_ref().unwrap().1
}
}
#[test]
fn test() {
let nums = vec![1, -1, -2, 4, -7, 3];
let k = 2;
let res = 7;
assert_eq!(Solution::max_result(nums, k), res);
let nums = vec![10, -5, -2, 4, 0, 3];
let k = 3;
let res = 17;
assert_eq!(Solution::max_result(nums, k), res);
let nums = vec![1, -5, -20, 4, -1, 3, -6, -3];
let k = 2;
let res = 0;
assert_eq!(Solution::max_result(nums, k), res);
}