300. Longest Increasing Subsequence

link

Method 1 Backtrack

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

            return res

        r = 0

        for i in range(n):
            r = max(r, backtrack(i))

        return r

Method 2 DP

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        n = len(nums)
        dp = [1] * n

        res = 1
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], 1 + dp[j]) 
                    res = max(res, dp[i])

        return res

Method 3 LIS

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        q = []
        
        for n in nums:
            
            idx = bisect.bisect_left(q, n)

            
            if idx == len(q):
                q.append(n)
                
            else:
                q[idx] = n
                
        return len(q)