Pythonで最長の循環増加部分列の長さを求めるプログラム

数値のリスト nums が与えられたとき、最長の増加部分列（LIS）の長さを求めることを考えます。ただし、この問題では部分列がリストの末尾に到達した後、先頭に戻って続くことができる、いわゆる「循環」を許容する点が特徴です。

問題の例

たとえば、入力が次の場合を考えてみましょう。

nums = [6, 5, 8, 2, 3, 4]

このとき出力は 5 になります。これは、最長の増加部分列が [2, 3, 4, 6, 8] となるためです。末尾の要素から先頭へ「折り返して」部分列を構成できる点に注目してください。

解法のアプローチ

循環を扱うために、元のリストを2回連結した配列を作成し、各開始位置から標準的なLISアルゴリズム（二分探索を用いた O(n log n) の手法）を適用します。手順は以下の通りです。

• 元のリストを2回繰り返した長さ2倍の配列 a を作成する
• 答えを格納する変数 ans を 0 で初期化する
• i を 0 から nums のサイズまで繰り返す
  • 空のリスト dp を用意する
  • j を i から (nums のサイズ + i - 1) まで繰り返す
    • n := a[j]
    • k := n を dp に挿入すべき最左のインデックス（二分探索）
    • k が dp のサイズと等しければ、n を dp の末尾に追加
    • そうでなければ、dp[k] を n で置き換え
    • ans := ans と dp のサイズの最大値
• ans を返す

ここで使っているのは、二分探索（bisect モジュール）を活用した効率的なLIS計算法です。dp リストには「その時点での増加部分列の候補」が昇順に保持され、各要素に対して挿入位置を求めることで全体を O(n log n) で処理できます。

実装例

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

import bisect

class Solution:
    def solve(self, nums):
        a = nums + nums          # リストを2回連結して循環を表現
        ans = 0
        for i in range(len(nums)):
            dp = []
            for j in range(i, len(nums) + i):
                n = a[j]
                k = bisect.bisect_left(dp, n)
                if k == len(dp):
                    dp.append(n)   # dp の末尾に追加
                else:
                    dp[k] = n      # 既存の値を置き換え
            ans = max(ans, len(dp))
        return ans

ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums))

入力

[4, 5, 8, 2, 3, 4]

出力

5

計算量について

このアルゴリズムの時間計算量は O(n² log n) です。開始位置ごとに O(n log n) のLIS計算を行うためです。空間計算量は O(n) となります。なお、リストを2倍に伸ばしていますが、内側のループは len(nums) 個の要素しか走査しないため、単純な全探索よりも効率的に動作します。

まとめ

循環増加部分列の問題は、「リストの連結による循環の表現」と「二分探索を使ったLISの高速化」を組み合わせることで解決できます。競技プログラミングやアルゴリズム学習において、LISの応用問題として非常に良い練習になるテーマです。