Pythonで最長のフィボナッチサブシーケンスの長さを見つけるプログラム

X_1、X_2、...のような1つのシーケンスがあるとすると、-

• n> =3

• X_i + X_i +1=すべてのi+2に対してX_i+2 <=n

ここで、シーケンスを形成する厳密に増加する配列Aを想定し、Aの最長のフィボナッチのようなサブシーケンスの長さを見つける必要があります。そのようなシーケンスがない場合は、0を返します。

したがって、入力がA =[1,2,3,4,5,6,7,8]のようである場合、次のシーケンス[1,2,3,5,8]があるため、出力は5になります。長さ5。

これを解決するには、次の手順に従います-

• sA：=Aの要素からの新しいセット

• last：=Aの最後の要素

• B：=Aに存在する各元素とその頻度を含むマップ

• 最高：=0

• Aのサイズが0までのiの場合、実行します

  • a：=A [i]

  • Aのサブ配列内の各bについて[インデックスi+1から終了まで]、実行

    • c：=a + b

    • cがsAに存在する場合、

      • B [a、b]：=1 + B [b、c]

      • ベスト：=ベストの最大値とB [a、b] +2

    • それ以外の場合、c>が最後の場合、

      • ループから出てきます

• 最高のリターン

例

理解を深めるために、次の実装を見てみましょう-

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