Pythonで最長のフィボナッチ型部分列の長さを求める方法を解説

数列 X₁, X₂, …, X_n が「フィボナッチ型」とみなされるのは、次の条件を満たす場合です。

• n >= 3 であること

• すべての i + 2 <= n について、X_i + X_i+1 = X_i+2 が成り立つこと

ここで、厳密に増加する配列 A が与えられたとします。このとき、A から選び出せる最も長いフィボナッチ型の部分列の長さを求めます。条件を満たす部分列が存在しない場合は 0 を返します。

たとえば、入力が A = [1,2,3,4,5,6,7,8] の場合、出力は 5 になります。これは、長さ 5 のフィボナッチ型部分列 [1,2,3,5,8] が存在するためです。

解法の考え方

この問題は、数列の後ろから順にペアを調べていく動的計画法のアプローチで効率的に解くことができます。具体的な手順は以下の通りです。

• sA := 配列 A のすべての要素を含む集合を作成する

• last := 配列 A の最後の要素を取得する

• B := ペアごとの値を記録するマップ（Counter）を初期化する

• best := 0 で初期化する

• i を配列 A の末尾から先頭へ向かって逆順にループする

  • a := A[i]

  • b を部分配列 A[i+1:] の各要素としてループする

    • c := a + b

    • c が sA に存在する場合

      • B[a,b] := 1 + B[b,c]

      • best := max(best, B[a,b] + 2)

    • それ以外で c > last となる場合

      • ループを抜ける

• 最後に best を返す

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

from collections import Counter
def solve(A):
    sA = set(A)
    last = A[-1]
    B = Counter()
    best = 0
    for i in reversed(range(len(A))):
        a = A[i]
        for b in A[i+1:]:
            c = a+b
            if c in sA:
                B[a,b] = 1 + B[b,c]
                best = max(best , B[a,b]+2)
            elif c>last:
                break
    return best

A = [1,2,3,4,5,6,7,8]
print(solve(A))

入力

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

出力

5