1340. Jump Game V (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def maxJumps(self, arr, d):
        """
        :type arr: List[int]
        :type d: int
        :rtype: int
        """
        dp = [1] * len(arr)
        h = {}
        for i, num in enumerate(arr):
            if num in h:
                h[num].append(i)
            else:
                h[num] = [i]
        nums = sorted(h.keys())
        for num in nums:
            for i in h[num]:
                j = i + 1
                while j < len(arr) and j - i <= d:
                    if arr[j] >= arr[i]:
                        break
                    dp[i] = max(dp[j] + 1, dp[i])
                    j += 1
                j = i - 1
                while j >= 0 and i - j <= d:
                    if arr[j] >= arr[i]:
                        break
                    dp[i] = max(dp[j] + 1, dp[i])
                    j -= 1
        return max(dp)