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.
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
stack = []
dp = [1] * (len(arr) + 1)
for i, v in enumerate(arr + [float('inf')]):
# This is using "<", not "<=", because if there are several same numbers, others can jump to either of them and either has a chance to be the optimal step. For different numbers within range, it is always good to jump to a larger number
while stack and arr[stack[-1]] < v:
last = stack.pop()
L = [last]
while stack and arr[stack[-1]] == arr[last]:
L.append(stack.pop())
for j in L:
if i - j <= d:
dp[i] = max(dp[i], dp[j] + 1)
if stack and j - stack[-1] <= d:
dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
stack.append(i)
dp[-1] = 0
return max(dp)