题解 | 最长上升子序列(一)贪心+二分 python

import bisect
import sys

l = int(input())
nums = list(map(int, input().split()))

res = [nums[0]]
for x in nums:
    if x > res[-1]:
        res.append(x)
        continue
    
    # linear search O(n)
    # for ind, y in enumerate(res):
    #     if x <= y:
    #         res[ind] = x
    #         break
    # bisearch O(logn)
    ind = bisect.bisect_left(res, x)
    res[ind] = x

print(len(res))