Pythonでリストから最長のフィボナッチ部分列の長さを求める方法

問題の概要

厳密に増加している正の整数からなるリスト nums が与えられたとします。このとき、すべての i > 1 に対して A[i] = A[i - 1] + A[i - 2] という関係(つまりフィボナッチ数列と同じ漸化式)を満たす、最も長い部分列 A(最小長は3)を見つけ、その長さを求めるのが課題です。

例えば、入力が nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] の場合、[1, 2, 3, 5, 8, 13] という部分列を選ぶことができるため、出力は 6 となります。

解決のための手順

この問題は、ペアごとにフィボナッチ的な連鎖を追跡していくことで解決できます。具体的な手順は以下の通りです。

• A := nums(入力リスト)
• n := A の要素数
• maxLen := 0(最大長の初期値)
• S := A から作成したセット(高速な存在判定用)
• i を 0 から n まで繰り返す:
  • j を i + 1 から n まで繰り返す:
    • x := A[j](現在の値)
    • y := A[i] + A[j](次に期待される値)
    • length := 2(初期の連鎖の長さ)
    • y が S に存在する間、以下を繰り返す:
      • z := x + y
      • x := y、y := z と更新
      • length を 1 増やす
      • maxLen := maxLen と length の大きい方
• maxLen > 2 であれば maxLen を返し、そうでなければ 0 を返す

ポイントは、リストが厳密に増加していることを利用し、セット S による O(1) の存在チェックで次のフィボナッチ項を素早く確認できる点です。これにより、全ての開始ペア (i, j) について連鎖を効率的に伸ばしていけます。

実装例

class Solution:
   def solve(self, nums):
      A = nums
      n = len(A)
      maxLen = 0
      S = set(A)
      for i in range(0, n):
         for j in range(i + 1, n):
            x = A[j]
            y = A[i] + A[j]
            length = 2
            while y in S:
               z = x + y
               x = y
               y = z
               length += 1
               maxLen = max(maxLen, length)
      if maxLen > 2:
         return maxLen
      else:
         return 0
ob = Solution()
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print(ob.solve(nums))

入力

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

出力

6

計算量について

外側の二重ループで全てのペアを試すため O(n²)、さらに各ペアからフィボナッチ連鎖を辿る処理が加わります。ただし、連鎖の各項は前の2項の和として急速に増大するため、実際の連鎖の深さは限られ、実用上は十分高速に動作します。条件を満たす部分列が見つからない場合は 0 が返される点にも注意してください。