Maximize Forward Jumps to the Last Array Index
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Maximize Forward Jumps to the Last Array Index
You are given a 0-indexed integer array `nums` of length `n` and an integer `target`. Start at index `0`.
A jump from index `i` to index `j` is allowed exactly when both conditions hold:
- `0 <= i < j < n`.
- `-target <= nums[j] - nums[i] <= target`.
Return the maximum number of jumps in a sequence that reaches index `n - 1`. If the last index cannot be reached, return `-1`.
### Examples
**Example 1**
```text
Input: nums = [2,4,3,8,5], target = 2
Output: 3
```
Jump along indices `0 -> 1 -> 2 -> 4`. The corresponding value differences are `2`, `-1`, and `2`, so all three jumps are allowed. Index `3` cannot be reached from any earlier index, so no valid route can use all five indices; three jumps is the maximum.
**Example 2**
```text
Input: nums = [0,4,8], target = 3
Output: -1
```
Neither later index is reachable directly from index `0`: their value differences are `4` and `8`. There is no first jump and hence no route to the last index.
### Constraints
- `2 <= nums.length == n <= 1000`.
- `-10^9 <= nums[i] <= 10^9`.
- `0 <= target <= 2 * 10^9`.
### Clarifying Questions
- Must a jump go to the next index? No; it may skip indices, provided both conditions hold.
- Can a jump go backward? No; the destination index must be strictly larger.
- Is the limit based on index distance or value difference? It constrains `nums[j] - nums[i]`, not `j - i`.
- Are repeated values allowed? Yes; no uniqueness constraint is given. Equal values permit a jump even when `target` is zero.
- Can a route stop at some other reachable index? No; only sequences ending at `n - 1` count toward the answer.
### C++ Interface
```cpp
class Solution {
public:
int maximumJumps(vector<int>& nums, int target) {
}
};
```
### Reasoning Checkpoints
- Preserve the requirement to end at the last index while maximizing the jump count.
- Distinguish an unreachable index from a reachable index with zero jumps.
- Retain the inclusive value-difference bounds and strictly forward index order.
```hint Reachable predecessors
For a sequence ending at index j, what must be true of its previous index and the best sequence reaching that previous index?
```
Overview: Find the largest number of strictly forward jumps that reaches the final array index while each value difference stays within the given inclusive target range.
