Problem statement

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

Solution 1

Let dp(i) be the maximum we can get if start with place i. Then for each node it is enough to check 2d places.

Complexity

Time complexity is O(nd), space is O(n).

Code

class Solution:
    def maxJumps(self, arr, d):
        n = len(arr)
        
        @lru_cache(None)
        def dp(i):
            ans = 1
            for j in range(i + 1, min(n, i + d + 1)):
                if arr[j] >= arr[i]: break
                ans = max(ans, dp(j) + 1)
            for j in range(i - 1, max(-1, i - d - 1), -1):
                if arr[j] >= arr[i]: break
                ans = max(ans, dp(j) + 1)
            return ans
        
        return max(dp(i) for i in range(n))

Solution 2

There is better solution, using monotonic stack idea. Let us try to build solution in opposite direction: then what we need to find for each index is the closest indexes to the right and to the left such that value in these indexes are greater than value at index. Then we have graph with at most 2n elements and the goal is to find the longest parts in this DAG, we again use dp.

Complexity

Time and space complexity is O(n)

Code

class Solution:
    def maxJumps(self, A, d):
        def jump(iterator):
            stack = []
            for i in iterator:
                while stack and A[stack[-1]] < A[i]:
                    j = stack.pop()
                    if abs(i - j) <= d: graph[j].append(i)
                stack.append(i)
        
        @lru_cache(None)
        def dp(i):
            return 1 + max(map(dp, graph[i]), default=0)
        
        n, graph = len(A), defaultdict(list)
        jump(range(n))
        jump(range(n-1, -1, -1))
        return max(dp(i) for i in range(n))