Pythonで最長増加部分列（LIS）の長さを求めるプログラム【二分探索でO(n log n)】

数値のリストが与えられたとき、その中から最長増加部分列（LIS: Longest Increasing Subsequence）の長さを求める問題を考えます。たとえば、入力が [6, 1, 7, 2, 8, 3, 4, 5] の場合、最長増加部分列は [2, 3, 4, 5, 6] となるため、答えは 5 になります。

本記事では、単純な動的計画法（O(n²)）よりも高速な、二分探索を組み合わせた O(n log n) のアルゴリズムをPythonで実装する方法を解説します。

アルゴリズムの手順

• nums と同じサイズの配列 tails を用意し、すべての要素を 0 で初期化します。

• size := 0 とします。

• nums の各要素 x に対して、以下の処理を行います。

  • i := 0、j := size とします。

  • i ≠ j である間、次を繰り返します。

    • mid := i + (j − i) / 2 とします。

    • tails[mid] < x ならば i := mid + 1、そうでなければ j := mid とします。

  • tails[i] := x とします。

  • size := max(i + 1, size) とします。

• 最後に size を返します。

なぜこのアルゴリズムが機能するのか

配列 tails[k] には、「長さ k+1 の増加部分列の末尾の値として考えられる最小値」が保存されます。この配列は常に昇順に保たれるため、新しい要素 x を挿入すべき位置を二分探索で O(log n) で特定できます。挿入位置が現在の size を超えた場合は、より長い増加部分列が見つかったことを意味し、size が更新されます。結果として、全体の計算量は O(n log n) に抑えられます。

Pythonでの実装例

class Solution(object):   def solve(self, nums):      tails = [0 for i in range(len(nums))]      size = 0      for x in nums:         i = 0         j = size         while i != j:            mid = i + (j - i) // 2            if tails[mid] < x:               i = mid + 1            else:               j = mid         tails[i] = x         size = max(i + 1, size)      return sizeob = Solution()nums = [7, 2, 8, 3, 9, 4, 5, 6]print(ob.solve(nums))

実行結果

入力：

[7, 2, 8, 3, 9, 4, 5, 6]

出力：

5

この入力では、最長増加部分列は [2, 3, 4, 5, 6] となり、その長さは 5 です。

まとめ

二分探索を活用することで、従来の O(n²) の動的計画法よりも大幅に高速に最長増加部分列の長さを求められます。要素数が多いデータ（数万〜数十万件規模）を扱う場合に特に有効な手法なので、競技プログラミングや実務のデータ処理でもぜひ活用してください。