Maximum Number of Jumps to Reach the Last Index

medium dp array

Problem

You are given a 0-indexed array nums of length n and an integer target. You start at index 0. From index i you may jump to any later index j (i < j < n) as long as the value change stays within the target gap, that is −target ≤ nums[j] − nums[i] ≤ target. Return the maximum number of jumps needed to reach index n−1, or −1 if it is impossible.

Inputnums = [1, 3, 6, 4, 1, 2], target = 2

Output3

Path 0 → 1 → 3 → 5 uses 3 jumps with gaps +2, +1, −2, all within ±2.

nums (comma-separated)

target

def maximum_jumps(nums, target):
    n = len(nums)
    dp = [-1] * n
    dp[0] = 0
    for i in range(1, n):
        for j in range(i):
            if dp[j] != -1 and abs(nums[i] - nums[j]) <= target:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp[n - 1]

function maximumJumps(nums, target) {
  const n = nums.length;
  const dp = new Array(n).fill(-1);
  dp[0] = 0;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] !== -1 && Math.abs(nums[i] - nums[j]) <= target)
        dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return dp[n - 1];
}

class Solution {
    public int maximumJumps(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] != -1 && Math.abs(nums[i] - nums[j]) <= target)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        return dp[n - 1];
    }
}

int maximumJumps(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> dp(n, -1);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] != -1 && abs(nums[i] - nums[j]) <= target)
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    return dp[n - 1];
}

Explanation

The question asks for the most jumps, not the fewest, so a greedy "jump as far as you can" rule does not work. We instead build the answer up index by index with dynamic programming.

Let dp[i] be the maximum number of jumps that can land us exactly on index i, starting from index 0. We seed dp[0] = 0 (we are already there, zero jumps). Every other entry starts at -1, meaning "not reachable yet".

To fill dp[i], we look back at every earlier index j < i. Index j is a legal launch point only if it is itself reachable (dp[j] != -1) and the value gap is allowed: |nums[i] - nums[j]| ≤ target. When both hold, arriving at i through j costs dp[j] + 1 jumps, and we keep the largest such value.

After the sweep, dp[n-1] holds the most jumps to the final index. If it is still -1, the last index was never reachable and we return -1.

Example: nums = [1,3,6,4,1,2], target = 2. The chain 0 → 1 → 3 → 5 has gaps +2, +1, -2, all within ±2, giving dp[5] = 3 — the answer.

Time: O(n²) Space: O(n)