最長増加部分列(LIS)の解法 ── AOJ 2430 対応の動的計画法
最長増加部分列 とは
配列の中から、厳密に増加する部分列の最大長を動的計画法で求める LIS 問題に取り組みます。本レッスンでは、最長増加部分列 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
最長増加部分列 (LIS)
最長増加部分列 (Longest Increasing Subsequence、略して LIS) は、与えられた数列の中から 必ずしも連続していない 増加列を抜き出したときの、最大の長さを求める問題です。例えば [10, 9, 2, 5, 3, 7, 101, 18] の場合、[2, 3, 7, 18] という長さ 4 の増加列が取り出せます。これが最長で、答えは 4 です。
部分列 (subsequence) と部分配列 (subarray) を混同しないでください。部分配列 は連続した区間を取り出すもの、部分列 は元の順番を保ちつつ要素を間引くもの、と区別します。LIS は後者です。
LIS は 株価のトレンド分析、バージョン管理での共通系列推定 など、現場でも応用が広い古典問題。
部分列と部分配列の違いを図で押さえる
LIS では 間を自由に飛ばせる ため、[2, 5, 7] も [2, 3, 7] も候補になります。連続性が無い分、ナイーブな線形走査では解けず、DP の出番になります。
O(n^2) DP の考え方
dp[i] を「i 番目の要素で 終わる LIS の長さ」と定義します。すると、i より前の j で nums[j] < nums[i] を満たすものについて、dp[i] は dp[j] + 1 の最大値となります。誰も伸ばせなければ単独の 1 です。
漸化式は dp[i] = max(dp[j] + 1 for j < i if nums[j] < nums[i])、最小は 1 です。最終的な答えは dp 全体の最大値となります。
DP は「終端を固定する」と一気に整理できる。
iで終わると決めてしまえば、jを遡って探索するだけで済む。
dp 配列の埋まり方を図で追う
nums = [10, 9, 2, 5, 3, 7, 101, 18] で dp がどう更新されるかを表でみていきます。
| i | nums[i] | 伸ばせる j の dp[j] | dp[i] | 説明 |
|---|---|---|---|---|
| 0 | 10 | — | 1 | 先頭。単独で長さ 1 |
| 1 | 9 | — | 1 | 9 < 10 で伸ばせず単独 |
| 2 | 2 | — | 1 | より小さい前者なし |
| 3 | 5 | dp[2]=1 | 2 | 2 -> 5 |
| 4 | 3 | dp[2]=1 | 2 | 2 -> 3 |
| 5 | 7 | dp[3]=2, dp[4]=2 | 3 | 2 -> 5 -> 7 or 2 -> 3 -> 7 |
| 6 | 101 | dp[5]=3 | 4 | 2 -> 5 -> 7 -> 101 |
| 7 | 18 | dp[5]=3 | 4 | 2 -> 5 -> 7 -> 18 |
最後に max(dp) = 4 が答えです。「i で終わる」を縦軸に取ると、各セルが独立に決まるので DP テーブルが破綻なく埋まる ことが直感的に分かります。
O(n log n) の高速版 (パッチェンス・ソート法)
さらに n log n で解くテクニックも存在し、これは patience sorting と呼ばれます。tails[k] を「長さ k+1 の増加列のうち、末尾の最小値」として管理し、新しい要素が来たら tails の中で 二分探索 して置き換えます。本レッスンでは扱いませんが、興味があれば挑戦してみてください。
dp の遷移を図解
点線が dp の遷移、つまり「自分より小さい要素から伸ばせる」関係です。2 -> 3 -> 7 -> 18 で長さ 4 のパスが取れるのが分かります。
Python 実装
Python
def lengthOfLIS(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)dp は全要素 1 で初期化します (自分だけでも長さ 1 の LIS なので)。二重ループで j < i かつ nums[j] < nums[i] のとき、dp[i] を dp[j] + 1 で更新します。最後に max(dp) を返せば完了です。計算量は O(n^2) です。
JavaScript 実装
JavaScript
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const n = nums.length;
const dp = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}ロジックは Python と同じです。Math.max(...dp) でスプレッド構文を使い、dp 配列の最大値を取得します。
計算量とトレードオフ
| 手法 | 時間 | 空間 | 復元 | 向いている場面 |
|---|---|---|---|---|
| 全列挙 (brute force) | O(2^n) | O(n) | 容易 | n <= 20 の検算用 |
| O(n^2) DP | O(n^2) | O(n) | 容易（親を記録） | n <= 5000、可読性重視 |
| O(n log n) patience | O(n log n) | O(n) | 一工夫必要 | n が大きいケース |
「LIS そのものを復元したい」ときは O(n^2) 版で parent[i] を持つのが一番ラクです。長さだけ欲しいなら patience の方が高速。
よくある間違い
1 つ目は 連続部分配列と混同 すること。LIS は飛び飛びで OK なので、[1, 100, 2, 3] の LIS は [1, 2, 3] で長さ 3 になります。[100] だけを切り取って 1 にはなりません。2 つ目は 厳密増加と非減少の取り違え。本問題は 厳密増加 なので nums[j] < nums[i] です。<= にすると同値要素も含まれてしまい誤答になります。3 つ目は 空配列 で max([]) を呼んでエラーになるパターン。最初に長さチェックを入れるのが安全です。
やってみよう
[7, 7, 7, 7, 7, 7]の LIS は1です。すべて同じ値なので増加できません。[1, 3, 6, 7, 9, 4, 10, 5, 6]を手計算してみる。答えは6(例1, 3, 6, 7, 9, 10)。- O(n log n) 版にも挑戦してみる。二分探索 と組み合わせた
patience sortingのアイデアが鍵です。
LIS は DP の代表例 であり、二分探索、Fenwick tree など、さまざまな応用問題の入口でもある。
よくある質問
Q. この内容は面接でよく聞かれますか？
A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。
Q. 計算量と空間計算量はどっちを優先しますか？
A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。
Q. 問題が解けないときどう取り組めば良いですか？
A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。
次のレッスン
次は 最大部分配列和 (Kadane) で、配列の中から、厳密に増加する部分列の最大長を動的計画法で求める LIS 問題に取り組みます を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 最長増加部分列 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 最長増加部分列 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 戻り値は厳密増加部分列の最大長 (整数)
- DP 配列 dp[i] = i 番目で終わる LIS の長さ、として O(n^2) で求めること
- 等しい値は増加とみなさない (nums[j] < nums[i] を満たす場合のみ伸ばす)
入出力例
test-cases.txt
lengthOfLIS([10,9,2,5,3,7,101,18]) → 4
lengthOfLIS([0,1,0,3,2,3]) → 4
lengthOfLIS([7,7,7,7]) → 1
lengthOfLIS([1,2,3,4,5]) → 5
lengthOfLIS([5,4,3,2,1]) → 1
lengthOfLIS([42]) → 1