Python에서 가장 긴 피보나치 부분 수열의 길이를 찾는 프로그램

<시간/>

X_1, X_2, ...와 같은 시퀀스가 하나 있다고 가정하고 X_n은 −

인 경우 피보나치와 유사합니다.

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
0에서 0까지의 A 크기의 i에 대해
- a :=A[i]
- A[인덱스 i+1에서 끝까지]의 하위 배열에 있는 각 b에 대해
  - c :=+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]