题解 | 最长不下降子序列

import sys
import bisect
n=int(input())
if n==0:
    print(0)
else:
    a=list(map(int,sys.stdin.read().split()))
    d=list()#用于存储最长不下降子序列
    d.append(a[0])
    for i in range(1,n):#
        #贪心算法每次向d中添加满足条件的最小元素，
        if a[i]>=d[-1]:
            d.append(a[i])
        else:
            #从d中找到，第一个大于a[i]的元素,并将其替换为a[i].
            #样做是因为，我们找到了一个长度与被替换元素所在位置对应的子序列，但其结尾更小（为 x）
            #这个更小的结尾为后续元素提供了更多成为不下降子序列一部分的可能性。
            pos=bisect.bisect_right(d,a[i])
            d[pos]=a[i]
print(len(d))