思路

$q$ 中存储每个长度下上升子序列末尾值的最小值，该数组一定严格单调递增，所以可以使用二分查找。

代码

# 手写二分
n = int(input())
N = n + 1
a = list(map(int, input().split()))
q = [0] * N

length = 0
for i in range(n):
    l, r = 0, length 
    while l < r:
        mid = l + r + 1 >> 1
        if q[mid] < a[i]:
            l = mid 
        else:
            r = mid - 1 
    length = max(length, r + 1)
    q[r + 1] = a[i]
print(length)

# 调用 bisect_right 
n = int(input())
a = list(map(int, input().split()))
INF = float('inf')
q = [INF] * (n + 1)
q[0] = -INF 
length = 0 
from bisect import bisect_right 
for i in range(n):
    idx = bisect_right(q, a[i])
    if idx - 1 >= 0 and q[idx - 1] == a[i]:
        idx -= 1
    q[idx] = a[i]
    length = max(length, idx)
print(length)