[leetcode]300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

 

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

class Solution(object):
    def lengthOfLIS(self, nums):
        sub =[]
        def binarySearch(sub, num):
            l,r = 0, len(sub)-1
            while l<=r:
                mid = (l+r)//2
                if sub[mid] == num :
                    return mid
                elif sub[mid] < num:
                    l = mid+1
                else :
                    r = mid-1
            return l
        
        for n in nums:
            pos = binarySearch(sub, n)
            #print(pos)
            if len(sub)== pos:
                sub.append(n)
            else:
                sub[pos] = n
        return len(sub)