Pythonで最長増加部分列（LIS）を二分探索で効率的に求める方法

ソートされていない整数のリストが与えられたとき、その中から「最長増加部分列（LIS：Longest Increasing Subsequence）」の長さを求める問題を考えてみましょう。

例えば、入力が [10, 9, 2, 5, 3, 7, 101, 18] の場合、増加する部分列としては [2, 3, 7, 101] が最長となるため、答えは 4 になります。

解法のアプローチ

この問題は、単純な動的計画法でも O(n²) で解けますが、「tails（末尾管理用の配列）」と二分探索を組み合わせることで、O(n log n) という高速な計算量で解くことができます。

手順は以下の通りです。

• tails := nums と同じ長さの配列を用意し、すべて 0 で初期化する
• size := 0 とする（現在判明している LIS の長さ）
• 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 の増加部分列の末尾としてあり得る最小の値」を常に保持している点です。新しい要素 x が来たとき、二分探索によって x を配置すべき位置を O(log n) で特定できます。

• x が tails の全要素より大きければ、LIS が 1 つ延びる（配列の末尾に追加）
• そうでなければ、既存の値を x で置き換えることで、将来より長い部分列を作りやすくする

これにより、各要素の処理が O(log n)、全体で O(n log n) に収まります。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
   def lengthOfLIS(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 size

ob1 = Solution()
print(ob1.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))

入力

[10, 9, 2, 5, 3, 7, 101, 18]

出力

4

処理の流れを追ってみる

各要素を処理したときの tails 配列の変化は次のようになります。

最終的な size が 4 となり、これが最長増加部分列の長さです。なお、tails 自体は必ずしも実際の部分列と一致するわけではありません（上の例では [2, 3, 7, 18] になっています）。あくまで「各長さにおける最小の末尾値」を管理するための補助配列である点に注意しましょう。

まとめ

最長増加部分列（LIS）は、二分探索を活用することで O(n log n) という高い効率で求められます。競技プログラミングや技術面接でも頻出のテーマなので、tails 配列の仕組みと二分探索の挙動をしっかり理解しておきましょう。