Problem Explanation:

The problem requires us to find the maximum number of indices you can visit, starting from any index of the array with the help of jumping. The only condition is that you can make a jump if and only if the jumping point value is the maximum between the both ends. You can make a jump d steps far either on the left side or on the right side.

An approach to solve this problem is to use the concept of Dynamic Programming and Decreasing Stack. We can initialize a DP table with size equals to the number of elements in the provided array where each element is equal to 1. This is because at least 1 position is visited at all times, which is the starting point. We can also initialize an empty stack that will store indices. Then for each index until the size of the provided array, perform the following steps:

• While the stack is not empty and the value of the current index in the array is either larger than the value at the index of the stack's top or it is the last index. Then,
  • Add the top of the stack to a temporary indices list and pop the stack.
  • If there are multiple equal values in the array, add all the respective indices in the stack to the temporary indices list and pop all the respective values from the stack.
  • Also if the current index is less or equals to d difference far from any index of the temporary indices list or the index of the stack's top then we can say that a jump can be made. Therefore, update the DP table's respective value which will be equal to the maximum between the current DP table's value or DP table's value of the index where the jump is found plus 1 because jump is possible.
• Add the current index to the stack.

Finally, the maximum value in the DP table is our result because it will show the maximum indices we can visit which is starting from any index of the array.

After understanding the approach, let's walk through an example provided in the problem statement. Suppose we have arr = [6,4,14,6,8,13,9,7,10,6,12] and d = 2 then the steps are as follow:

• Initialize a DP table with 1, DP = [1,1,1,1,1,1,1,1,1,1,1] and an empty stack.
• Loop through each index in the arr, index = 0.
  • Stack is empty so directly push index 0 to the stack.
  • Stack = [0]
• Next index 1, 6 < 4 and it doesn't mean the criteria so push index 1 to the stack. Stack = [0, 1]
• Next index 2, 4 < 14 and it means the criteria so consider all the indices in the stack until we find a larger value, in our case, it's 6 which is at index 0 so it will remain in the stack.
  • Indices = [1], pop index 1 from the stack so the Stack = [0]
  • Now check if a jump is possible,
    • Jump is not possible from index 2 to 1 because 1 - 2 > d or not, it's not so skip this.
    • Jump is possible from index 0 to 1 because 1 - 0 < = d, therefore,
      • Update the DP[0], DP[0] = max(DP[0], DP[1]+1), DP = [2,1,1,1,1,1,1,1,1,1,1]
• Push the index 2 to the stack, Stack = [0,2]
• If we follow this process until the last index, our DP table will look like this DP = [2,1,5,2,3,4,3,3,3,2,4]
• Therefore, the maximum elements we can visit starting from any index of the array is max(DP) i.e 5.

Python Solution:

1
2python
3class Solution:
4    def maxJumps(self, arr, d: int) -> int:
5        n = len(arr)
6        dp = [1] * n
7        stack = []
8
9        for i in list(range(n)) + list(range(n - 1, -1, -1)):
10            while stack and (i-d <= stack[-1] <= i+d) and arr[stack[-1]] < arr[i]:
11                j = stack.pop()
12                if stack and (i-d <= stack[-1] <= i+d) and arr[stack[-1]] < arr[j]:
13                    dp[j] = max(dp[j], dp[stack[-1]] + 1)
14                if stack and arr[stack[-1]] == arr[j]:
15                    continue
16                if i < n:
17                    dp[i] = max(dp[i], dp[j] + 1)
18            stack.append(i)
19
20        return max(dp)

Javascript Solution:

1
2javascript
3var maxJumps = function(arr, d) {
4    let n = arr.length;
5    let dp = Array(n).fill(1), stack = [];
6
7    for(let i of [...Array(n).keys()].concat([...Array(n).keys()].reverse())){
8        while(stack.length && i-d <= stack[stack.length-1] && stack[stack.length-1] <= i+d && arr[stack[stack.length-1]] < arr[i]){
9            let j = stack.pop();
10            if(stack.length && i-d <= stack[stack.length-1] && stack[stack.length-1] <= i+d && arr[stack[stack.length-1]] < arr[j])
11                dp[j] = Math.max(dp[j], dp[stack[stack.length-1]]+1);
12            if(stack.length && arr[stack[stack.length-1]] == arr[j]) continue;
13            if(i < n)
14                dp[i] = Math.max(dp[i], dp[j]+1);
15        }
16        stack.push(i);
17    }
18
19    return Math.max(...dp);
20};

Java Solution:

1
2java
3class Solution {
4    public int maxJumps(int[] arr, int d) {
5        int n = arr.length;
6        int[] dp = new int[n];
7        Arrays.fill(dp, 1);
8        Deque<Integer> stack = new LinkedList<Integer>();
9
10        for(int i: IntStream.concat(IntStream.range(0,n), IntStream.range(n-1,-1,-1)).toArray()){
11            while(!stack.isEmpty() && i-d <= stack.peekLast() && stack.peekLast() <= i+d && arr[stack.peekLast()] < arr[i]){
12                int j = stack.pollLast();
13                if(!stack.isEmpty() && i-d <= stack.peekLast() && stack.peekLast() <= i+d && arr[stack.peekLast()] < arr[j])
14                    dp[j] = Math.max(dp[j], dp[stack.peekLast()]+1);
15                if(!stack.isEmpty() && arr[stack.peekLast()] == arr[j]) 
16                    continue;
17                if(i < n)
18                    dp[i] = Math.max(dp[i], dp[j]+1);
19            }
20            stack.addLast(i);
21        }
22
23        return Arrays.stream(dp).max().getAsInt();
24    }
25}

C++ Solution:

1
2c++
3class Solution {
4public:
5    int maxJumps(vector<int>& arr, int d) {
6        int n = arr.size();
7        vector<int> dp(n, 1);
8        stack<int> stack;
9    
10        for (int i = 0; i <= 2*n - 1; ++i) {
11            int idx = (i < n) ? i : (2*n -1 - i);
12            while (!stack.empty() && arr[stack.top()] < arr[idx]) {
13                int j = stack.top(); stack.pop();
14                if (!stack.empty() && abs(stack.top() - j) <= d) 
15                    dp[stack.top()] = max(dp[stack.top()], dp[j] + 1);
16                if (i < n && abs(idx - j) <= d)
17                    dp[idx] = max(dp[idx], dp[j] + 1);
18            }
19            stack.push(idx);
20        }
21    
22        return *max_element(begin(dp), end(dp));
23    }
24};

C# Solution:

1
2csharp
3public class Solution {
4    public int MaxJumps(int[] arr, int d) {
5        int n = arr.Length;
6        int[] dp = new int[n];
7        Stack<int> stack = new Stack<int>();
8        Array.Fill(dp, 1);
9        
10        for(int i = 0; i < 2*n; ++i){
11            int idx = (i < n) ? i : (2*n -1 - i);
12            while(stack.Any() && arr[stack.Peek()] < arr[idx]){
13                int j = stack.Pop();
14                if(stack.Any() && Math.Abs(stack.Peek() - j) <= d)
15                    dp[stack.Peek()] = Math.Max(dp[stack.Peek()], dp[j] + 1);
16                if(i < n && Math.Abs(idx - j) <= d)
17                    dp[idx] = Math.Max(dp[idx], dp[j] + 1);
18            }
19            stack.Push(idx);
20        }
21        
22        return dp.Max();
23    }
24}

The above explanation and solutions make use of dynamic programming and the concept of decreasing stack to determine the maximum indices that can be jumped starting from any index in the array under specified conditions.

This problem can be visualized by imagining the given array as a mountain range. You start from any mountain and can only jump to the higher mountains within a given distance 'd'. The dynamic programming approach creates a table 'dp' initially filled up with 1's (as each index in the array can be visited at least once). Then the solution employs the logic of decreasing stack to update the 'dp' table. The stack keeps track of the indices that can be jumped from any starting point and populates the top of the stack with the index of the maximum height.

This process continues all through the array and at the same time, the 'dp' table is updated by drawing comparisons between the existing and new maximum indices reachable via jumps. The final answer to the problem is derived by taking the maximum value from the 'dp' table which represents the maximum number of indices that can be visited.

Note that this approach is utilized in generating solutions in Python, Javascript, Java, C++, and C# languages. All these solutions follow a similar logic and differ only in their syntax.

So, that brings us to the end of the problem. If you understand the concept of dynamic programming and decreasing stack, this problem is a great application to practice those concepts.