蟻本 2-3 最長増加部分列問題 - 競プロ

蟻本 2-3 最長増加部分列問題

code: python

from bisect import bisect_left

n = int(input())

a = list(map(int, input().split()))

dp = float("inf") * n

# dpi := 長さが i + 1 であるような増加部分列における最終要素の最小値（存在しない場合は INF）

for i in range(n):

dp[bisect_left(dp, ai)] = ai

print(bisect_left(dp, float("inf")))

テーマ