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

（python版本！）
刚开始用的动态规划的解法，虽然超时了，但是自己写出来了很开心！！！

class Solution:
    def LIS(self , arr ):
        def func1(li):
            return len(li)
        def func2(li):
            return ''.join(list(map(str,li)))
        res=[[arr[i]] for i in range(len(arr))] #res[i]表示以arr[i]为结尾的最长递增子序列的元素集合
        for i in range(1,len(arr)):
            for j in range(i):
                if(arr[j]<arr[i]):
                    if(len(res[j])+1>len(res[i])):
                        temp=list(res[j])
                        temp.append(arr[i])
                        res[i]=temp
                    elif(len(res[j])+1==len(res[i])): #如果相等则比较字典序
                        temp=list(res[j])
                        temp.append(arr[i])
                        str_j=''.join(list(map(str,temp)))
                        str_i=''.join(list(map(str,res[i])))
                        if(str_j<str_i):
                            res[i]=temp
        print(res)
        anses=[]
        max_len=len(max(res,key=func1))
        for i in range(len(res)):
            if(len(res[i])==max_len):
                anses.append(res[i])
        ans=min(anses,key=func2)
        return ans

arr=[2,1,5,3,6,4,8,9,7]
res=Solution().LIS(arr)
print(res)

于是又看了大佬们的解析，根据面向测试用例编程，写出来了贪心+二分的解法！

class Solution:
    def LIS(self,arr):
        max_len=[1]*len(arr)  #max_len[i]表示以arr[i]为结尾的最长递增子序列的长度
        vec=[]
        #vec存放递增子序列,vec的长度即使最长递增子序列的长度但并不一定是答案
        #如果arr[i]>vec[-1],直接添加arr[i];否则在vec中寻找第一个比arr[i]大的元素，替换之
        vec.append(arr[0])
        for i in range(1,len(arr)):
            if(arr[i]>vec[-1]):
                vec.append(arr[i])
                max_len[i]=len(vec)
            elif(arr[i]<=vec[-1]):
                #调用二分搜索寻找第一个比arr[i]大的元素
                idx=self.binary_search(vec,arr[i])
                vec[idx]=arr[i]
                max_len[i]=idx+1
        print(max_len)
        len_vec=len(vec)
        res=[0]*len_vec
        for i in range(len(max_len)-1,-1,-1):
            if(max_len[i]==len_vec):
                res[len_vec-1]=arr[i]
                len_vec-=1
        return res


    def binary_search(self,vec,x):
        #寻找第一个比x大于等于的元素，仅适用于本题，x<vec[-1]的情况。
        left=0
        right=len(vec)-1
        while(left<=right):
            mid = left + (right - left) // 2
            if(x==vec[mid]):
                return mid
            elif(x<vec[mid]):
                right=mid-1
            elif(x>vec[mid]):
                left=mid+1
        return left

if(__name__=='__main__'):
    #line=list(map(int,input().strip().split()))
    line=[1,3,8,6,5,2,5]
    res=Solution().LIS(line)
    print(res)