1696. 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`

1696. Jump Game VI
``````struct 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));
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);
}
``````