Leetcode-300-Longest Increasing Subsequece

300.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           

Solution:

if __name__== "__main__":
    def lengthOfLIS(nums):
        tails = [0 for _ in range(len(nums))]
        size = 0
        for x in nums:
            i, j = 0, size
            while i != j:
                m = (i+j)//2
                if tails[m]<x:
                    i = m+1
                else:
                    j = m
            tails[i] = x
            size = max(i+1, size)
        return size
    print(lengthOfLIS([10,9,2,5,3,7,101,18]))
           

tails存放升序尾節點，随着for x in nums: 周遊，tails數組的變化依次為：

[10, 0, 0, 0, 0, 0, 0, 0]
 [9, 0, 0, 0, 0, 0, 0, 0]
 [2, 0, 0, 0, 0, 0, 0, 0]
 [2, 5, 0, 0, 0, 0, 0, 0]
 [2, 3, 0, 0, 0, 0, 0, 0]
 [2, 3, 7, 0, 0, 0, 0, 0]
 [2, 3, 7, 101, 0, 0, 0, 0]
 [2, 3, 7, 18, 0, 0, 0, 0]
           

size儲存目前最大的遞增子序列長度。