1964. Find the Longest Valid Obstacle Course at Each Position - Explanation

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        n = len(obstacles)
        dp = [[-1] * (n + 1) for _ in range(n)]

        def dfs(i, prev):
            if i < 0:
                return 0
            if dp[i][prev] != -1:
                return dp[i][prev]

            res = dfs(i - 1, prev)
            if prev == n or obstacles[prev] >= obstacles[i]:
                res = max(res, 1 + dfs(i - 1, i))
            dp[i][prev] = res
            return res

        dfs(n - 1, n)
        return [1] + [1 + dp[i - 1][i] for i in range(1, n)]

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        res = []
        dp = [10**8] * (len(obstacles) + 1)

        for num in obstacles:
            index = bisect.bisect(dp, num)
            res.append(index + 1)
            dp[index] = num

        return res

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        res = []
        dp = []

        for num in obstacles:
            index = bisect.bisect_right(dp, num)
            res.append(index + 1)

            if index == len(dp):
                dp.append(num)
            else:
                dp[index] = num

        return res