最長増加部分列問題 (Longest Increasing Subsequence, LIS) は、与えられた数列の中で、順序を変えずに要素を取り出して作る部分列のうち、増加列（各要素が前の要素より大きい）の中で最も長いものを求める問題です。例えば、数列 [3, 1, 4, 1, 5, 9, 2, 6] の最長増加部分列は [1, 4, 5, 9] や [1, 2, 6] などで、その最長の長さは 4 です。
最長増加部分列問題を解くことの意義
LIS は、一見単純な問題に見えますが、以下のような応用があり、アルゴリズムの基礎を学ぶ上で重要です。
- バイオインフォマティクス: DNA 配列の解析など、配列データにおけるパターン発見に利用されます。
- データ圧縮: データの変化パターンを捉えるために利用されることがあります。
- 株価分析: 株価のトレンド分析など、時系列データの解析に利用されることがあります。
- アルゴリズム競技: 動的計画法や二分探索といった、より高度なアルゴリズムを学ぶための基礎となります。
この問題は、動的計画法または二分探索を使って解くことができます。Python での実装例とともに、それぞれの解法を解説します。
1. 動的計画法による解法
動的計画法では、部分問題を解いてその結果を記録し、それを利用してより大きな問題を解きます。
考え方
dp[i]:i番目の要素を最後尾とする最長増加部分列の長さ と定義します。dp[i]を求めるには、iより前の要素jについて、nums[j] < nums[i]ならば、dp[j] + 1がdp[i]の候補となります。- これは、
j番目の要素を最後尾とする最長増加部分列に、i番目の要素を付け加えることができる場合、その長さはdp[j] + 1になる、ということを意味します。
- これは、
dp[i]は、これらの候補の中で最大のものです。- つまり、
i番目の要素を最後尾とする最長増加部分列は、iより前の要素を最後尾とする最長増加部分列の中で、i番目の要素を付け加えることができるもののうち、最も長いものにi番目の要素を付け加えたものになります。
- つまり、
初期状態
- すべての
iに対してdp[i] = 1(自分自身のみからなる部分列の長さは 1)
実装例
まず、最もシンプルなコードを示します。
def lis_dp_simple(nums): n = len(nums) dp = [1] * n # 初期値は全て1 # i を 0 から n-1 まで動かす for i in range(n): # j を 0 から i-1 まで動かす for j in range(i): # nums[j] < nums[i] ならば、dp[i] を更新する候補 if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) # より大きい方で更新 return max(dp) # dp の最大値が LIS の長さ # 使用例 nums = [3, 1, 4, 1, 5, 9, 2, 6] length = lis_dp_simple(nums) print(f"最長増加部分列の長さ: {length}") # 出力: 最長増加部分列の長さ: 4
上記のlis_dp_simple関数では、リストdpを用意し、全ての要素を1で初期化しています。
外側のループでnumsの各要素nums[i]について、内側のループでそれより前の要素nums[j]を調べ、nums[j] < nums[i]であればdp[i]をdp[j] + 1と比較し、大きい方の値で更新します。
最終的にdpの中の最大値が最長増加部分列の長さになります。
次に、最長増加部分列そのものを返すようにコードを改良します。
def lis_dp_full(nums): n = len(nums) dp = [1] * n prev = [-1] * n # 直前の要素のインデックスを記録 for i in range(n): for j in range(i): if nums[j] < nums[i] and dp[i] < dp[j] + 1: dp[i] = dp[j] + 1 prev[i] = j # 更新時に直前の要素を記録 # 最長増加部分列の最後尾のインデックスを見つける max_len = max(dp) end_index = dp.index(max_len) # 最長増加部分列を復元 lis = [] while end_index != -1: lis.append(nums[end_index]) end_index = prev[end_index] return lis[::-1] # 逆順にして返す # 使用例 nums = [3, 1, 4, 1, 5, 9, 2, 6] result = lis_dp_full(nums) print(f"最長増加部分列: {result}") # 出力例: 最長増加部分列: [1, 4, 5, 9]
lis_dp_full関数では、最長増加部分列を復元するために、prevリストを追加しています。
prev[i]にはnums[i]を最後尾とする最長増加部分列で、nums[i]の直前の要素のインデックスを記録します。
dpリストの最大値を持つ要素のインデックスend_indexから始めて、prevを辿ることで最長増加部分列を復元できます。
計算量
- 時間計算量: O(n2) (二重ループのため)
- 空間計算量: O(n) (
dp配列のため)
2. 二分探索による解法
二分探索を用いると、より効率的に LIS を求めることができます。
考え方
tails[i]: 長さがi+1である増加部分列の最後尾の要素のうち、最小のもの と定義します。tailsは常に増加列になります。numsの各要素xについて、xがtailsのどの要素よりも大きければ、xをtailsに追加します。(LIS の長さが 1 増える)- そうでなければ、
tails中でx以上の最小の要素をxで置き換えます。(LIS の長さは変わらないが、より小さい値で終わる LIS を見つけたことになる)
実装例
import bisect def lis_binary_search(nums): tails = [] # 各長さの増加部分列の最後尾の最小値を格納 for x in nums: # x が tails のどの要素よりも大きい場合、末尾に追加 if not tails or x > tails[-1]: tails.append(x) else: # tails の中で x 以上の最小の要素を二分探索で探し、x で置き換える idx = bisect.bisect_left(tails, x) # x を挿入すべき位置 tails[idx] = x return len(tails) # tailsの長さがLIS # 使用例 nums = [3, 1, 4, 1, 5, 9, 2, 6] length = lis_binary_search(nums) print(f"最長増加部分列の長さ: {length}") # 出力: 最長増加部分列の長さ: 4
上記のlis_binary_search関数では、tailsリストを用いて増加部分列の最後尾の最小値を管理します。
numsの各要素xについて、xがtailsの最後の要素より大きければtailsに追加します。
そうでない場合は、bisect.bisect_left関数を用いてtailsの中でx以上の最小の要素を見つけ、xで置き換えます。
最終的にtailsの長さが最長増加部分列の長さになります。
bisect.bisect_left(a, x)は、ソート済みのリストaに対して、xを挿入できる最も左の位置を返します。
最長増加部分列の要素を復元するコードを以下に示します。
import bisect def lis_binary_search_full(nums): tails = [] predecessors = {} for x in nums: if not tails or x > tails[-1]: if tails: predecessors[x] = tails[-1] tails.append(x) else: idx = bisect.bisect_left(tails, x) if idx > 0: predecessors[x] = tails[idx - 1] tails[idx] = x # 最長増加部分列を復元する longest_subsequence = [] current = tails[-1] while current is not None: longest_subsequence.append(current) current = predecessors.get(current) return longest_subsequence[::-1] # 逆順にして返す # 使用例 nums = [3, 1, 4, 1, 5, 9, 2, 6] result = lis_binary_search_full(nums) print(f"最長増加部分列: {result}") # 出力例: 最長増加部分列: [1, 2, 5, 9]
lis_binary_search_full 関数では、predecessors ディクショナリを使用して、各要素がどの要素の後に続くかを記録しています。
tails リストを更新する際に、新しい要素が既存の要素を置き換える場合や、新しい要素が tails に追加される場合に、predecessors を更新します。
最長増加部分列を復元する際は、tails の最後の要素から始めて、predecessors を辿って前の要素を順に追加していくことで復元します。
計算量
- 時間計算量: O(n log n) (
numsの各要素について二分探索を行うため) - 空間計算量: O(n) (
tails配列のため)
まとめ
| 解法 | 時間計算量 | 空間計算量 | 特徴 |
|---|---|---|---|
| 動的計画法 | O(n2) | O(n) | 実装が比較的簡単。最長増加部分列自体も復元しやすい。 |
| 二分探索 | O(n log n) | O(n) | 高速。n が大きい場合に有利。最長増加部分列自体の復元は、工夫が必要(上記コード参照)。 |
Python では bisect モジュールを使うことで、二分探索を簡潔に記述できます。最長増加部分列問題は、アルゴリズムの理解を深めるのに役立つ問題です。
[PR]
