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

Rust Solution

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[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);
}

Having problems with this solution? Click here to submit an issue on github.