Python in O(nlgn)


  • 0
    A
    def lengthOfLIS(self, nums):
        # http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
        size = len(nums)
        if size <= 1:
            return size
            
        tails = [nums[0]]
        ans = 0
        
        for x in nums[1:]:
            if x > tails[-1]:
                tails.append(x)
            else:# replace this to the most potential position
                beg, end = 0, len(tails)
                while beg != end:
                    mid = (beg+end)/2
                    if tails[mid] < x:
                        beg = mid + 1
                    else:
                        end = mid
                tails[beg] = x
                    
        return len(tails)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.