题解 | 最长上升子序列(一)

#2.使用二分查找，动态构建一个辅助数组 res 来记录当前能够构成的上升子序列的“最小末尾元素”
import sys
from bisect import bisect_left

n=int(sys.stdin.readline())
a=[int(x) for x in sys.stdin.readline().split()]
res=[]

for x in a:
    i=bisect_left(res,x)#返回的是 第一个不小于 x 的位置。如果 x 已经在数组中，它返回 x 第一个出现的位置
    if i==len(res):#比res最后一个元素还大
        res.append(x)
    else:
        res[i]=x
print(len(res))


#1.dp求解
# import sys

# def longest_inc_seq():
#     n=int(sys.stdin.readline())
#     a=[int(x) for x in sys.stdin.readline().split()]
    
#     if n<=1:
#         return n

#     dp=[1]*n
#     for i in range(n):
#         for j in range(i):
#             if a[i]>a[j]:
#                 dp[i]=max(dp[i],dp[j]+1)

#     return max(dp)
# print(longest_inc_seq())