最長増加部分列
O(n^2) DP と O(n log n) のテクニックを学びます
「最長増加部分列」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
LISとは何か
部分列は要素を飛ばしても順序を保ちます。最長増加部分列とは、そのような部分列のうち、値が厳密に増加するものの最長の長さです。
a = [3, 1, 4, 1, 5, 9, 2]部分列であり、部分配列ではない
部分配列とは異なり、LISは連続している必要がありません。小さい数を飛ばしながら、増加するつながりを保てます。
O(n^2)のDP状態
dp[i]を、インデックスiで終わるLISの長さとします。どの要素も、それ単体で長さ1の部分列になるため、少なくとも1です。
dp = [1] * nO(n^2)の遷移
各iについて、それより前にあるすべてのjを調べます。a[j]が小さければ、dp[i] = max(dp[i], dp[j] + 1)として部分列を延長します。
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)答えを読み取る
LISは最後のインデックスだけでなくどこで終わってもよいため、答えは表の最大値です。
answer = max(dp)O(n^2)でTLEになる理由
二重ループの計算量はO(nの2乗)です。nが100000近くになると遅すぎて、時間制限超過になります。
ペイシェンスソートの考え方
高速な方法では、各部分列の長さについて実現可能な末尾の最小値をリストに保持します。ペイシェンスソートと同じ考え方です。
tails = []bisectで配置する
各数について、bisect_leftで末尾の値の中から入る位置を二分探索します。これにより、全体の計算量はO(n log n)になります。
from bisect import bisect_left延長するか置き換えるか
位置が末尾より後ろなら、appendしてLISを伸ばします。それ以外の場合は、その末尾の値をより小さい値で上書きします。
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x長さはtailsに入っている
走査が終わると、len(tails)がLISの長さになります。リスト自体が常にその部分列になるわけではありませんが、長さは正確です。
answer = len(tails)厳密増加と非減少
非減少の変種ではbisect_rightに切り替え、同じ値でもつながりを延長できるようにします。
from bisect import bisect_right確認問題
O(n log n)でLISの長さを求める方法はどれでしょうか。
まとめ：n^2からn log nへ
これでLISを2通りの方法で解けるようになりました。O(n^2)のDPは単純ですが、末尾の値とbisectを使う方法は大きな入力にも対応でき、時間制限を超えません。
よくある質問
「最長増加部分列」レッスンは無料ですか？
はい。「最長増加部分列」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「最長増加部分列」で何を学びますか？
O(n^2) DP と O(n log n) のテクニックを学びます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「最長増加部分列」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。