LC 0300 [M] Longest Increasing Subsequence (LIS) - ALawliet/algorithms GitHub Wiki

the binary search solution is recommended and optimal and genius

# O(nlogn) solution with binary search
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:        
        def binarySearch(A, x):
            l = 0
            r = len(A) - 1
            while l <= r:
                m = (l + r) // 2
                if A[m] == x:
                    return m
                elif A[m] < x:
                    l = m + 1
                elif A[m] > x:
                    r = m - 1
            return l
        
        res = []
        for x in nums:
            # l = binarySearch(res, x)
            l = bisect_left(res, x)
            if l == len(res):
                res.append(x)
            else:
                res[l] = x
        return len(res)

here note the final solution is not at [-1] but the max of the DP table

most intuitive

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        T = [1] * n
        for r in range(1, n):
            for l in range(r):
                if nums[r] > nums[l]:
                    T[r] = max(T[r], T[l] + 1)
        return max(T)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        LIS = [1] * len(nums)
        
        for i in range(len(nums) - 1, -1, -1):
            for j in range(i + 1, len(nums)):
                if nums[i] < nums[j]:
                    LIS[i] = max(LIS[i], 1 + LIS[j])
        
        return max(LIS)

recursion memoization

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:        
        @cache
        def dp(r):
            res = 1
            for l in range(r):
                if nums[r] > nums[l]:
                    res = max(res, dp(l) + 1)
            return res
        
        n = len(nums)
        res = 1
        for r in range(n):
            res = max(res, dp(r))
        return res

class Solution():
    def lengthOfLIS(self, nums):
        n = len(nums)
        
        memo = [0 for i in range(n)]
        
        def maxAt(r):
            if memo[r]: return memo[r]

            res = 1
    
            for l in range(r):
                if nums[r] > nums[l]:
                    res = max(res, maxAt(l) + 1)

            memo[r] = res
            return res
        
        res = 1
        for r in range(n):
            res = max(res, maxAt(r))
        return res