Leetcode 1340. Jump Game V

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        stat = {}
        n = len(arr)
        visited = {}
        nums = 0
        for i in range(n):
            nums = max(nums, self.dfs(arr, i, visited, d))
        return nums


    def dfs(self, arr, current, visited, d):
        if current in visited:
            return visited[current]
        n = len(arr)
        count = 0
        i = current - 1
        thres = max(-1, current - d - 1)
        while i > thres and arr[i] < arr[current]:
            temp = self.dfs(arr, i, visited, d)
            visited[i] = temp
            count = max(count, temp)
            i -= 1
        i = current + 1
        thres = min(n, current + d + 1)
        while i <  thres and arr[i] < arr[current]:
            temp = self.dfs(arr, i, visited, d)
            visited[i] = temp
            count = max(count, temp)
            i += 1
        return count + 1

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        indexes = sorted(range(len(arr)), key=lambda i: arr[i])
        n = len(arr)
        dp = [1] * n
        nums = 0
        for current in indexes:
            i = current - 1
            thres = max(-1, current - d - 1)
            count = 0
            while i > thres and arr[i] < arr[current]:
                count = max(count, dp[i])
                i -= 1
            i = current + 1
            thres = min(n, current + d + 1)
            while i < thres and arr[i] < arr[current]:
                count = max(count, dp[i])
                i += 1
            dp[current] += count
            nums = max(nums, dp[current])
        return nums