最長増加部分列問題(Longest Increasing Subsequence, LIS)は、与えられた数列の中で、任意の要素を取り出して並べた部分列のうち、昇順になっている最長のものを見つける問題です。例えば、[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7]という数列があるとき、その最長増加部分列は[1, 2, 5, 8, 9]です。
この問題は、動的計画法や二分探索を使って効率的に解くことができます。以下では、Pythonでそれぞれの方法を実装して解説します。
動的計画法による解法
動的計画法は、前処理を行っておくことで、任意のiに対して、i以下の位置での最長増加部分列を求めることができます。i以下の位置での最長増加部分列の長さをdp[i]とすると、以下のような再帰式が得られます。
dp[i] = max(dp[j] + 1) for j in range(i) if a[j] < a[i]
これは、a[j]がa[i]よりも小さい場合、dp[j]に1を加えたものの中で最大のものを求めることを表しています。この再帰式を用いて、dp[n-1]が最長増加部分列の長さとなります。
以下がPythonでの実装例です。
def LIS_dp(nums): 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)
この実装例では、numsが与えられた数列、dpが動的計画法で求めたi以下の位置での最長増加部分列の長さを格納するリストとなっています。
二分探索による解法
二分探索による解法は、動的計画法に比べて計算量が少ないため、大きなデータセットに対しても効率的に処理することができます。具体的なアルゴリズムは以下の通りです。
- リストAに、最長増加部分列を保持する
- 数列の要素xに対して、以下の処理を行う
- xがAの最後尾よりも大きい場合、Aの最後尾にxを追加する
- xがAの最後尾以下の場合、Aの中でxよりも大きい最小の要素を二分探索で探し、その位置にxを挿入する
最終的に、Aの長さが求める最長増加部分列の長さとなります。
以下がPythonでの実装例です。
import bisect def LIS_bs(nums): A = [] for x in nums: i = bisect.bisect_left(A, x) if i == len(A): A.append(x) else: A[i] = x return len(A)
この実装例では、bisectモジュールを使用して二分探索を行っています。bisect_leftは、Aの中でxよりも大きい最小の要素を二分探索で探し、その位置を返す関数です。Aの最後尾にxを追加する場合は、Aの長さが増えるため、最長増加部分列の長さも1増えます。
まとめ
以上がPythonで最長増加部分列問題を解く方法についての解説となります。動的計画法と二分探索の両方のアルゴリズムを理解しておくと、より広い範囲の問題に対して対応できるようになります。これらのプログラムはPythonの基本的な文法とライブラリで実装することができます。Pythonの基礎学習には下記のようなサイトの利用が有効です。
