LISと「同じ長さなら末尾を小さく」

最長増加部分列は、元の順序を保っていくつか選び、値が厳密に増える列です。連続している必要はありません。

言語：Python / 計算量：O(N log N)

前提：二分探索は「境界」を探す

考え方

1. tails[k] は長さ k+1 の増加列で最小の末尾。
2. x 以上の最初の位置を二分探索。
3. その場所を x に置き換え、なければ伸ばします。

具体例

[3,1,2] では tails は [3]→[1]→[1,2]。答えは2。小さい末尾ほど後ろにつなぎやすいことが根拠です。

実装

from bisect import bisect_left
tails=[]
for x in [3,1,2]:
    i=bisect_left(tails,x)
    if i==len(tails):tails.append(x)
    else:tails[i]=x
print(len(tails))

注意する条件

非減少列なら bisect_right。tails 自体が元の数列の部分列とは限りません。復元には前の添字が必要です。

確認問題

[2,2,2] の厳密増加LISの長さは？

実装課題

N と配列 A。厳密増加部分列の最大長。1 ≤ N ≤ 200000、|A_i| ≤ 10^9。

入力:
3
3 1 2
出力:
2

from bisect import bisect_left
n=int(input());a=list(map(int,input().split()))
t=[]
for x in a:
    i=bisect_left(t,x)
    if i==len(t):t.append(x)
    else:t[i]=x
print(len(t))

読了の記録・下書き・メモへ