题解 | #最长递增子序列#

# 采用贪心法+二分法。使用maxlen存储对应元素的最大递增序列长度；tmp存储实际值
# 概念1：当新加入的元素i比末尾元素大时，满足递增---直接加入； 若比末尾元素小，则
# 采用二分法寻找第一个比该元素大的数，并将其替换为i
# 以[2,1,5,3,6,4,8,9,7]为例。最初mexlen=[1];tmp=[2]. 
# 加入1，比tmp[-1]小，因此将2替换为1---tmp=[1],maxlen=[1,1] 
# 加入5，比tmp[-1]大，直接加入---tmp=[1,5],maxlen=[1,1,2]
# 加入3，比tmp[-1]小，因此将5替换为3---tmp=[1,3],maxlen=[1,1,2,2].... 
# 最后tmp=[1,3,4,7,9]; maxlen=[1,1,2,2,3,3,4,5,4] 
# 概念2：len(tmp)表示最大长度，但是并不一定是最终值。len(maxlen)表示arr的长度
# maxlen[-2]=5,表示对应的arr[-2]是最大递增序列的末尾，同理maxlen[-3]=4，表示
# 对用的arr[-3]为倒数第二位； 1,2,2,2是因为有很多种组合，字典序按最小排列，故去最前方的值
class Solution:
    def LIS(self , arr ):
        if len(arr)<2: return arr 

        self.index=None  #构建二分查找，查找第一个比i大的元素位置
        def binary_find(arr,left,right,target):
            if left>right: return 
            mid=int(left+(right-left)/2) 
            if arr[mid]>=target: #注意>=,因为可能存在4，4
                self.index=mid
                return binary_find(arr, left, mid-1, target)
            elif arr[mid]<target: 
                return binary_find(arr, mid+1, right, target)

        maxlen,tmp=[1],[arr[0]]
        for i in arr[1:]: 
            if i>tmp[-1]: 
                tmp.append(i)
                maxlen.append(len(tmp)) 
            else: 
                binary_find(tmp,0, len(tmp)-1, i) 
                tmp[self.index]=i 
                maxlen.append(len(tmp[:self.index+1])) 

        length=len(tmp)  #实际的最大长度
        for i in range(len(arr)-1,-1,-1): 
            if maxlen[i]==length: 
                tmp[length-1]=arr[i] 
                length-=1

        return tmp
        # write code here