C++에서 가장 긴 피보나치 수열의 길이

<시간/>

시퀀스 X_1, X_2, ..., X_n이 다음과 같은 경우 피보나치와 같다고 가정합니다.

n>=3
X_i + X_{i+1} =모든 i + 2 <=n
에 대해 X_{i+2}

이제 시퀀스를 형성하는 양의 정수로 구성된 엄격하게 증가하는 배열 A를 가정하고 A의 가장 긴 피보나치 유사 부분 시퀀스의 길이를 찾아야 합니다. 존재하지 않는 경우 0을 반환합니다. 따라서 숫자가 [1,2 ,3,4,5,6,7,8]이면 출력은 5가 됩니다. 피보나치인 가장 긴 부분 수열은 [1,2,3,5,8]과 같습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ret :=0
맵 생성 m, n :=배열 A의 크기
n x n 크기의 dp라는 행렬을 만듭니다.
0 ~ n – 1 범위의 i에 대해
- m[A[i]] :=i
- 범위 i – 1의 j에 대해 0까지
  - 필수 :=A[i] – A[j]
  - A[i] – A[j]
    - dp[i, j] :=최대 dp[i, j], dp[j, m[A[i] – A[j]]] + 1
  - 그렇지 않으면 dp[i,j] :=dp[i, j] 및 2의 최대값
  - ret :=ret 및 dp[i,j]
    의 최대값
ret>=3일 때 ret를 반환하고 그렇지 않으면 0을 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int lenLongestFibSubseq(vector<int> & A) {
      int ret = 0;
      unordered_map <int, int> m;
      int n = A.size();
      vector < vector <int> > dp(n, vector <int>(n));
      for(int i = 0; i < n; i++){
         m[A[i]] = i;
         for(int j = i - 1; j >= 0; j--){
            int req = A[i] - A[j];
            if(A[i] - A[j] < A[j] && m.count(A[i] - A[j])){
               dp[i][j] = max(dp[i][j], dp[j][m[A[i] - A[j]]] + 1);
            }else{
               dp[i][j] = max(dp[i][j], 2);
            }
            ret = max(ret, dp[i][j]);
         }
      }
      return ret >= 3 ? ret : 0;
   }
};
main(){
   vector<int> v = {1,2,3,4,5,6,7,8};
   Solution ob;
   cout << (ob.lenLongestFibSubseq(v));
}

입력

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