300. Longest Increasing Subseque

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #list to keep track of the longest increasing list, the elements are only as placeholders, they are not necessarily the actual longest increasing list 
        #dynamic programming: everytime we scan a number, the status of which is recorded in the LIS
        LIS=[]
        def insert(target):
            #use binary search to find the index of the element in LIS that is no less than the target 
            left,right=0,len(LIS)-1
            while left<=right:
                mid=left+(right-left)/2
                if LIS[mid]>=target:
                    right=mid-1
                else:
                    left=mid+1
                
            #if all the elements in the LIS is smaller than the target, then append the target to LIS
            if left==len(LIS):
                LIS.append(target)
            else:#otherwise, replace the element in the LIS with target, this does not affect the length of the actual LIS already found, but it would not be the actual LIS. 
                #all the elements after the replaced elements become placeholders that keep track of length of the previously found LIS. when we've replaced all the elements on and after the target elements, we've located a new LIS.  
                LIS[left]=target
        for num in nums: 
             insert(num)
        return len(LIS)