Problem
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.
Example 1:
Input: nums = [1,3,6,4,1,2], target = 2
Output: 3
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 3.
- Jump from index 3 to index 5.
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.
Example 2:
Input: nums = [1,3,6,4,1,2], target = 3
Output: 5
Explanation: To go from index 0 to index n - 1 with the maximum number of jumps, you can perform the following jumping sequence:
- Jump from index 0 to index 1.
- Jump from index 1 to index 2.
- Jump from index 2 to index 3.
- Jump from index 3 to index 4.
- Jump from index 4 to index 5.
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.
Example 3:
Input: nums = [1,3,6,4,1,2], target = 0
Output: -1
Explanation: It can be proven that there is no jumping sequence that goes from 0 to n - 1. Hence, the answer is -1.
Constraints:
2 <= nums.length == n <= 1000-109 <= nums[i] <= 1090 <= target <= 2 * 109
Solution (Java)
class Solution {
public int maximumJumps(int[] nums, int target) {
int []dp = new int[nums.length];
dp[0] = 0;//0 jump required to reach the dirst element
for (int i = 1;i<nums.length;++i)
dp[i] = Integer.MIN_VALUE;
for (int i = 1;i<nums.length;++i) {
//check if we can reach till i
for (int j = 0;j<i;++j) {
//condition given in question
if (Math.abs(nums[j]-nums[i])<=target)
{
//update dp if preiously reached index is not MIN Value
if (dp[j] != Integer.MIN_VALUE)
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
}
return dp[nums.length-1] == Integer.MIN_VALUE ? -1 : dp[nums.length-1];
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).