300. Longest Increasing Subsequence - LeetCode

from bisect import bisect_left


class SolutionDp:  # O(n*n) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 1, [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    result = max(result, dp[i])
        return result


class SolutionBs:  # O(n*log(n)) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 0, [0] * len(nums)
        for num in nums:
            lo = bisect_left(dp, num, hi=result)
            result, dp[lo] = max(result, lo + 1), num
        return result


class SolutionBsLessSpace:  # O(n*log(n)) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 0, []
        for i in range(len(nums)):
            if dp and nums[i] <= dp[-1]:
                dp[bisect_left(dp, nums[i])] = nums[i]
            else:
                result += 1
                dp.append(nums[i])
        return result


class SolutionBsInPlace:  # O(n*log(n)) / O(1)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result = 0
        for i in range(len(nums)):
            lo = bisect_left(nums, nums[i], hi=result)
            result, nums[lo] = max(result, lo + 1), nums[i]
        return result