最长递增子序列 python

n=int(input())
arr=list(map(int,input().split()))
dp,helper=[1]*n,[arr[0]]
# helper 长度为i的LIS末尾的数 helper才是真的dp 
# dp存放以i结尾的序列长度
import bisect  # 系统二分查找
def mybisect(a,num):   # 自己写的二分查找
    def bi(l,r,num):
        if l==r:
            return l
        mid=(l+r)//2
        if a[mid]>=num:
            r=mid
        elif a[mid]<num:
            l=mid+1
        return bi(l,r,num)
    return bi(0,len(a)-1,num)
for i,a in enumerate(arr[1:],1):  # index,value 从index1开始
    if a>helper[-1]:
        helper.append(a)
        dp[i]=len(helper)
    else:
        # pos=bisect.bisect_left(helper,a) # 找到可替换的值 此时a<=helper[pos] a>helper[pos-1]
        pos=mybisect(helper,a) # 找到可替换的值 此时a<=helper[pos] a>helper[pos-1]
        dp[i]=pos+1  # pos从0开始，dp从1开始
        helper[pos]=a
end,length=helper[-1],len(helper)
index=n-1-arr[::-1].index(end)  # 倒着找，前面的可能不够
res=[]
while index>=0:
    if res==[] or (arr[index]<res[-1] and dp[index]==length):  # 注意not res 等同于 res==[], 而非res==None，会报错~~
        res.append(arr[index])
        length-=1
    if not length:
        break
    index-=1
print(' '.join(map(str,res[::-1])))