2770. Maximum Number of Jumps to Reach the Last Index Medium

1/**
2 * [2770] Maximum Number of Jumps to Reach the Last Index
3 *
4 * You are given a 0-indexed array nums of n integers and an integer target.
5 * You are initially positioned at index 0. In one step, you can jump from index i to any index j such that:
6 * 
7 * 	0 <= i < j < n
8 * 	-target <= nums[j] - nums[i] <= target
9 * 
10 * Return the maximum number of jumps you can make to reach index n - 1.
11 * If there is no way to reach index n - 1, return -1.
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: nums = [1,3,6,4,1,2], target = 2
16 * Output: 3
17 * Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
18 * - Jump from index 0 to index 1. 
19 * - Jump from index 1 to index 3.
20 * - Jump from index 3 to index 5.
21 * It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 3 jumps. Hence, the answer is 3. 
22 * <strong class="example">Example 2:
23 * 
24 * Input: nums = [1,3,6,4,1,2], target = 3
25 * Output: 5
26 * Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
27 * - Jump from index 0 to index 1.
28 * - Jump from index 1 to index 2.
29 * - Jump from index 2 to index 3.
30 * - Jump from index 3 to index 4.
31 * - Jump from index 4 to index 5.
32 * It can be proven that there is no other jumping sequence that goes from 0 to n - 1 with more than 5 jumps. Hence, the answer is 5. 
33 * <strong class="example">Example 3:
34 * 
35 * Input: nums = [1,3,6,4,1,2], target = 0
36 * Output: -1
37 * Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1. 
38 * 
39 *  
40 * Constraints:
41 * 
42 * 	2 <= nums.length == n <= 1000
43 * 	-10^9 <= nums[i] <= 10^9
44 * 	0 <= target <= 2 * 10^9
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/maximum-number-of-jumps-to-reach-the-last-index/
50// discuss: https://leetcode.com/problems/maximum-number-of-jumps-to-reach-the-last-index/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn maximum_jumps(nums: Vec<i32>, target: i32) -> i32 {
56        0
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2770() {
68    }
69}
70