题解 | 最长不下降子序列

本题若使用dp[i]记录以第i个元素结尾的最长不降序序列长度，则需使用双层循环，运行超时。故想到使用二分查找，用列表d记录：到当前元素为止的最长不降序的序列 且该序列最后元素最小（为后续达到最长提供更大的可能性）。最后得到的即为这个最长不降序列。

import bisect
n=int(input())
v=list(map(int,input().split()))
d=[]
for num in v:
    index=bisect.bisect_right(d,num)       #bisect_right(d,num)得到列表d中第一个大于num的数字索引
    if index==len(d):
        d.append(num)
    else:
        d[index]=num                       #进行替换，确保最大可能性
print(len(d))