Maximum number of jumps to reach the last index

Array Dynamic Programming

32.5% acceptance

Feb 25, 2026

475

You are given a 0-indexed array nums of n integers and an integer target. You are initially positioned at index 0. In one step, you can jump from index i to any index j such that: 0 <= i < j < n -target <= nums[j] - nums[i] <= target Return the maximum number of jumps you can make to reach index n - 1. If there is no way to reach index n - 1, return -1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_jumps(nums: Vec<i32>, target: i32) -> i32 {
    let n = nums.len();
    let mut dp = vec![-1i32; n];
    dp[0] = 0;
    for j in 1..n {
      for i in 0..j {
        if dp[i] >= 0 && (nums[j] - nums[i]).abs() <= target {
          dp[j] = dp[j].max(dp[i] + 1);
        }
      }
    }
    dp[n - 1]
  }
}