【競プロ】広義単調増加数列と狭義単調増加数列の最大数【O(N log N)】

狭義単調増加数列の最大数

from bisect import bisect_left

N = 5
INF = 10**20

A = [2, 1, 4, 5, 5]
B = [INF]*(N+1)

for a in A:
    B[bisect_left(B, a)] = a
ans = bisect_left(B, INF)

アルゴリズムの詳細

広義単調増加数列の最大数

等しいことを認めるので bisect_right を使う

from bisect import bisect_left, bisect_right

N = 5
INF = 10**20

A = [2, 1, 4, 5, 5]
B = [INF]*(N+1)

for a in A:
    B[bisect_right(B, a)] = a
ans = bisect_left(B, INF)

単調減少数列の場合

逆から見れば良い

A = [2, 1, 4, 5, 5]
A = list(reversed(A))

# 略