Algorithm
Jump Game V
Solution
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
seen = dict()
def dfs(pos):
if pos in seen:
return
seen[pos] = 1
i = pos - 1
while i >= 0 and pos - i <= d and arr[pos] > arr[i]:
dfs(i)
seen[pos] = max(seen[pos], seen[i] + 1)
i -= 1
i = pos + 1
while i < len(arr) and i - pos <= d and arr[pos] > arr[i]:
dfs(i)
seen[pos] = max(seen[pos], seen[i] + 1)
i += 1
for i in range(len(arr)):
dfs(i)
return max(seen.values())Time Complexity
O(ND)
Space Complexity
O(N)
