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


	i + x where:&nbsp;i + x &lt; arr.length and  0 &lt;&nbsp;x &lt;= d.
	i - x where:&nbsp;i - x &gt;= 0 and  0 &lt;&nbsp;x &lt;= d.


In addition, you can only jump from index i to index j&nbsp;if arr[i] &gt; arr[j] and arr[i] &gt; arr[k] for all indices k between i and j (More formally min(i,&nbsp;j) &lt; k &lt; max(i, j)).

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

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

&nbsp;
Example 1:

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 --&gt; 8 --&gt; 6 --&gt; 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 &gt; 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 &gt; 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. 


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 1000
	1 &lt;= arr[i] &lt;= 105
	1 &lt;= d &lt;= arr.length


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        sorted_arr = []
        for i in range(n):
            sorted_arr.append((arr[i], i))
        sorted_arr.sort(reverse = True)
        depth = [1 for i in range(n)]
        while(sorted_arr):
            val, i = sorted_arr.pop()
            for j in range(i-1, max(-1, i-d-1), -1):
                if(arr[j] >= arr[i]):
                    break
                depth[i] = max(depth[j] + 1, depth[i])
            for j in range(i+1, min(n, i+d+1)):
                if(arr[j] >= arr[i]):
                    break
                depth[i] = max(depth[j] + 1, depth[i])
        return max(depth)
class Solution {
    public int maxJumps(int[] arr, int d) {
        List jumpsFrom[] =  new List[arr.length];  //find all possible jumps from each spot
        findJumps (arr,d,true,jumpsFrom); // add left jumps (itareting left to right)
        findJumps (arr,d,false,jumpsFrom); // add right jumps
        int jumpChain[] = new int[arr.length] , max = 1; // 0 - unvisited
        for (int i = 0 ; i < arr.length; i++) {
            if (jumpChain[i] == 0) {
                jumpChain[i] = dfs(arr, jumpChain, jumpsFrom, i);
                max = Math.max(max, jumpChain[i]);
            }
        }
        return max;
    }

    private void findJumps(int[] arr, int d, boolean left , List jumpsFrom[]){
        Stack<Integer> s = new Stack();
        int i = (left) ? 0 : arr.length - 1;
        while (i >=0  && i < arr.length){
            if (left) jumpsFrom[i] = new ArrayList();
            while (!s.isEmpty() && arr[i] > arr[s.peek()]){ // pop stack until higher step found from left/right, adding all left/right lower jumps from i
                int lowerIndex = s.pop(); 
                if (Math.abs(i - lowerIndex) <= d) jumpsFrom[i].add(lowerIndex); 
                else s = new Stack(); // past d steps
            }
            s.push(i);
            i += (left) ? 1 : -1;
        }
    }

    private int dfs(int[] arr , int jumpChain[], List<Integer> jumpsFrom[], int start){
        int max = 1;
        for (int i: jumpsFrom[start]) {
            if (jumpChain[i] == 0) jumpChain[i] = dfs(arr, jumpChain, jumpsFrom, i);
            max = Math.max (max , 1 + jumpChain[i]);
        }
        return max;
    }

}
class Solution {
    vector<int> dp;
    int countJumps(vector<int>& arr, int i, int d){
        if(dp[i]!=-1) return dp[i];
        int jumps = 0;
        int k = 1;
        while(k <= d && k + i < arr.size()){
            if(arr[k+i] < arr[i]){
                jumps = max(countJumps(arr, k+i, d)+1, jumps);
                k++;
            }
            else{
                break;
            }
        }
        k = 1;
        while(k <= d && i - k >= 0){
            if(arr[i] > arr[i - k]){
                jumps = max(countJumps(arr, i-k, d)+1, jumps);
                k++;
            }
            else{
                break;
            }
        }
        return dp[i] = jumps;
    }
public:
    int maxJumps(vector<int>& arr, int d) {
        dp.resize(arr.size(), -1);
        int maxJumps = 0;
        int n = arr.size();
        for(int i = 0; i < n; i++){
            maxJumps = max(countJumps(arr, i, d), maxJumps);
        }
        return maxJumps + 1;
    }
};
var maxJumps = function(arr, d) {

    let n = arr.length;
    let dp = new Array(n).fill(0);
    let result = 0;

    // Time complexity:
    // O(nlogn) + O(n*d) => O(ologn)

    // First we sort the arr (small -> large) , then calculating DP by sortedArr.
    // O(nlogn)
    let sortedArr = arr.map((v,i)=>([v,i])).sort((a,b)=>a[0]-b[0]);

    // Shifting with single way
    // mid -> left ; mid -> right
    // O(n*d)
    for(let index=1 ; index< n; index++){
        let [v,i] = sortedArr[index];

        for(let shift =1 ; shift <=d ; shift++){
            if(i+shift >= n || arr[i+shift] >= arr[i]) break;
            dp[i] = Math.max(dp[i],dp[i+shift]+1);
            if(dp[i] > result) result = dp[i];
        };

        for(let shift=-1 ; shift >= -d; shift--){
            if(i+shift < 0 || arr[i+shift] >= arr[i]) break;
            dp[i] = Math.max(dp[i],dp[i+shift]+1);
            if(dp[i] > result) result = dp[i];
        };
    };

    return result+1;

};
Jump Game V