Leetcode 1466 Solution

This article provides solution to leetcode question 1466 (jump-game-v)
Categories:
Tags:
Access this page by simply typing in "lcs 1466" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/jump-game-v

Solution

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        memo = [None] * len(arr)

        def cal(i):
            nonlocal arr
            nonlocal memo

            if memo[i] is not None:
                return memo[i]

            ans = 1

            j = i - 1
            tall = 0
            while j >= 0 and i - j <= d:
                if arr[j] >= arr[i]:
                    break
                if arr[j] >= tall:
                    ans = max(ans, cal(j) + 1)
                tall = max(tall, arr[j])
                j -= 1

            j = i + 1
            tall = 0
            while j < len(arr) and j - i <= d:
                if arr[j] >= arr[i]:
                    break
                if arr[j] >= tall:
                    ans = max(ans, cal(j) + 1)
                tall = max(tall, arr[j])
                j += 1

            memo[i] = ans
            return ans

        for i in range(len(arr)):
            cal(i)

        return max(memo)