Learning On the Way

300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

def lengthOfLIS(self, nums: List[int]) -> int: 
    trail = [] 
    for num in nums: 
        i = bisect_left(trail, num) 
        if i == len(trail): 
            trail.append(num) 
        else: 
            trail[i] = num 
    return len(trail)