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 :=숫자
n :=A의 크기
maxLen :=0
S :=A의 새로운 세트
0에서 n 사이의 i에 대해
- i + 1에서 n 사이의 j에 대해 다음을 수행합니다.
  - x :=A[j]
  - y :=A[i] + A[j]
  - 길이:=2
  - y가 S에 있는 동안 do
    - 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]