Method1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        #TC: O(n^2) 
        #SC: O(n) n = len(nums)

        dp = [1]*len(nums)

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

        return max(dp)

Method 2:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [] #dp[i]: among the ending values of all subsequences of length i+1, the smallest ending value
        #Then dp always keeps increeasing
        #When looping through nums and look at each ele, finding a loc to insert/update num according to the defination of dp


        def bisect_left(array, ele):
            #################################
            #Make sure to include the situation where ele in not in array
            if len(array) == 0:
                return 0
            if ele > array[-1]:
                return len(array)
            if ele < array[0]:
                return 0
            ######################################


            left = 0
            right = len(array) - 1
            while left + 1 < right:
                mid = left + (right - left) // 2
                if array[mid] == ele:
                    right = mid
                elif array[mid] < ele:
                    left = mid
                else:
                    right = mid

            if array[left] == ele:
                return left
            else:
                return right

        for ele in nums:
            #Using the library
            #InsertLoc = bisect.bisect_left(dp, ele)
            InsertLoc = bisect_left(dp, ele)        

            if InsertLoc == len(dp):
                dp.append(ele)
            else:
                dp[InsertLoc] = ele

        return len(dp)