> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/jump-game-v.md).

# Jump Game V

Given an array of integers `arr` and an integer `d`. In one step you can jump from index `i` to index:

* `i + x` where: `i + x < arr.length` and `0 < x <= d`.
* `i - x` where: `i - x >= 0` and `0 < x <= d`.

In addition, you can only jump from index `i` to index `j` if `arr[i] > arr[j]` and `arr[i] > arr[k]` for all indices `k` between `i` and `j` (More formally `min(i, j) < k < max(i, j)`).

You can choose any index of the array and start jumping. Return *the maximum number of indices* you can visit.

Notice that you can not jump outside of the array at any time.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/01/23/meta-chart.jpeg)

```
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.
```

**Example 2:**

```
Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.
```

**Example 3:**

```
Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies. 
```

**Example 4:**

```
Input: arr = [7,1,7,1,7,1], d = 2
Output: 2
```

**Example 5:**

```
Input: arr = [66], d = 1
Output: 1
```

**Constraints:**

* `1 <= arr.length <= 1000`
* `1 <= arr[i] <= 10^5`
* `1 <= d <= arr.length`

```java
class Solution {
    static class Pair {
        int h, i;

        // h -> height, i-> index
        Pair(int h, int i) {
            this.h = h;
            this.i = i;
        }
    }

    public int maxJumps(int[] nums, int d) {
        Pair[] arr = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++)
            arr[i] = new Pair(nums[i], i);
        // Sorting on basis of height
        // This helps in running our recursion from less dependent variables to more
        // dependent variables
        Arrays.sort(arr, (a, b) -> a.h - b.h);
        int[] dp = new int[nums.length];
        Arrays.fill(dp, -1);
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i].i;
            // Base case -> If we start at a index, we can count it as 1
            dp[index] = 1;
            int lower = Math.max(0, index - d);
            int upper = Math.min(nums.length - 1, index + d);
            // Making sure all the buildings are lower, if we were to make a jump
            for (int j = index - 1; j >= lower && nums[j] < nums[index]; j--)
                if (dp[j] != -1)
                    dp[index] = Math.max(dp[index], dp[j] + 1);
            for (int j = index + 1; j <= upper && nums[j] < nums[index]; j++)
                if (dp[j] != -1)
                    dp[index] = Math.max(dp[index], dp[j] + 1);
            max = Math.max(max, dp[index]);
        }
        return max;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/jump-game-v.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.