最長増加部分列(LIS)の長さの求め方
概要
数列 \(A_n\) の増加部分列とは「すべての \(i < j\) で \(A_i < A_j\) を満たす部分列」と定義される。
この増加部分列のうち、その長さが最長となるものを 最長増加部分列 (LIS: Longest Increasing Subsequence) と呼ぶ。
例えば「\(3, 1, 4, 1, 5, 9, 2, 6\)」の最長増加部分列の 1 つは「\(1, 4, 5, 6\)」で長さは 4 になる。
アルゴリズム
- 長さ \(n\) の増加部分列の最後の数を記録する配列 \(L_n\) を用意する。初期値はすべて∞とする。
- 数列 \(A_n\) を先頭から順番に見ていき、その値で \(L_n\) を更新していく。この時 \(L_n\) が 狭義単調増加 となるように埋めていく。また \(L_n\) は できるだけ小さい値で更新 をおこなう。
Warning
これで求められるのはLISの長さのみで、具体的な最長増加部分列は求められない
計算量
アルゴリズムの手順 2 で更新位置を決める際に単純に数列の先頭から見ていく場合は \(O(N^2)\)
\(L_n\) は狭義単調増加となるように更新を行うため、2 分探索で更新位置を決めることで改善できる。このときは \(O(N\log{}N)\)。
例
・初期状態
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(L_n\) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
・\(A_1=3\)
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(L_n\) | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
・\(A_2=1\)
\(A_1=3>1=A_2\) なので \(L_1\) を 1 で更新する。
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(L_n\) | 1 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
・\(A_3=4\)
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(L_n\) | 1 | 4 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
・\(A_4=1\)
狭義単調増加となるように 1 を追加できる場所がないため更新を行わない。
・最終結果
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(L_n\) | 1 | 2 | 5 | 6 | ∞ | ∞ | ∞ | ∞ |
\(n=4\) まで \(L_n\) が更新されているので数列 \(A_n\) の LIS は 4 となる。