Jump game vi

Array Dynamic Programming Queue Heap (Priority Queue) Monotonic Queue

46.4% acceptance

Feb 25, 2026

3552

125

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_result(nums: Vec<i32>, k: i32) -> i32 {
    use std::collections::VecDeque;
    let n = nums.len();
    let k = k as usize;
    let mut dp = vec![0i32; n];
    dp[0] = nums[0];
    // deque stores indices in decreasing order of dp value
    let mut deque: VecDeque<usize> = VecDeque::new();
    deque.push_back(0);
    for i in 1..n {
      // remove out-of-window indices
      while !deque.is_empty() && deque.front().copied().unwrap() + k < i {
        deque.pop_front();
      }
      dp[i] = nums[i] + dp[deque.front().copied().unwrap()];
      // maintain decreasing order
      while !deque.is_empty() && dp[deque.back().copied().unwrap()] <= dp[i] {
        deque.pop_back();
      }
      deque.push_back(i);
    }
    dp[n - 1]
  }
}