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]のような場合、出力は6になります。 [1、2、3、5、8、13]。

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

• A：=nums
• n：=Aのサイズ
• maxLen：=0
• S：=Aからの新しいセット
• 0からnの範囲のiについては、
  • i + 1からnの範囲のjについては、
    • x：=A [j]
    • y：=A [i] + A [j]
    • 長さ：=2
    • yがSに存在する間、実行します
      • z：=x + y
      • x：=y
      • y：=z
      • 長さ：=長さ+ 1
      • maxLen：=maxLenの最大値、長さ
• maxLen> 2の場合、
  • maxLenを返す
• それ以外の場合、
  • 0を返す

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

例

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