首页 > 最长递增子序列 python
头像
鱼201911010108744
编辑于 2020-08-06 14:25
+ 关注

最长递增子序列 python

最长递增子序列
重点是:输出序列而非最大长度!
题目:给定长度arr,设长度为n,输出arr的最大增量子序列。(如果有多个答案,请输出其中字典序最小的
时间复杂度:O(nlogn)

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])))



全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐