最長増加部分列とは？
最長増加部分列(LIS, Longest Increasing Subsequence)は、数列で順序を保ちつつ値が増加し続ける最長部分列の長さを求める問題です。例えば [10, 9, 2, 5, 3, 7, 101, 18] のLISは [2, 3, 7, 101] で長さ4です(連続でなくてよい)。
核心の一行: 「各値で終わる最長の増加列を追跡する」。 素朴にはO(n²)、賢くはO(n log n)です。
解法1: O(n²)のDP
dp[i] = i番目の要素で終わるLISの長さ。
dp[i] = max(dp[j] + 1)(j < i かつ arr[j] < arr[i])
各iで前方を全て見るのでO(n²)です。直感的でLISの復元も容易です。
解法2: O(n log n) — tails + 二分探索
tails[k] = 長さk+1の増加部分列の取り得る最後の値のうち最小値。
この tails は常に増加するので二分探索が可能です。新しい値 x に対して
- •
tailsでx以上の最初の位置を二分探索し、そこをxに置換します。 - •そんな位置がなければ(xが最大)
tailsの末尾に追加します。
最後に tails の長さがLISの長さです。より小さい最後の値を保つほど後ろにより多くの値を繋げられる、というのが核心の直感です。
動作原理(O(n log n))
ステップ1. 空の tails 配列で始めます。
ステップ2. 各要素 x について、tails で x が入る位置を二分探索します。
ステップ3. その位置で置換、末尾なら追加します。
ステップ4. 全要素を処理した後、tails の長さが答えです。
AlgoNoteの可視化は、各新値がtails配列のどの位置を置換/拡張するかをステップごとに示します。
時間計算量と空間計算量
| 方法 | 時間 | 空間 |
|---|---|---|
| DP | O(n²) | O(n) |
| tails + 二分探索 | O(n log n) | O(n) |
例で追ってみる
[10, 9, 2, 5, 3, 7, 101, 18]:
- •tailsの変化: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
- •最終tails長4 → LIS長4
よくあるミス
- •tailsを実際のLISと勘違い: tailsは長さだけ正確です。実際の列の復元には別途追跡(インデックス記録)が必要です。
- •増加の定義: 厳密増加なら
lower_bound、非減少を許すならupper_boundを使います。 - •二分探索の境界: 置換位置を誤ると長さがずれます。
AlgoNoteで直接確認しましょう
新しい値が来るたびにtails配列のどの位置が置換・拡張されるかをAlgoNoteでステップごとに確認できます。