C ++中最长斐波那契子序列的长度

假设我们有一个序列X_1，X_2，...，X_n如斐波那契式-

• n> = 3

• 所有i + 2 <= n的X_i + X_ {i + 1} = X_ {i + 2}

现在假设一个正整数的数组A严格增加，形成一个序列，我们必须找到A的最长斐波那契式子序列的长度。如果一个不存在，则返回0。因此，如果该数字类似于[1,2 ，3,4,5,6,7,8]，则输出将为5。最长的子序列是Fibonacci，就像[1,2,3,5,8]。

为了解决这个问题，我们将遵循以下步骤-

• ret：= 0

• 创建一个映射m，n：=数组A的大小

• 创建一个大小为nxn的称为dp的矩阵

• 对于i，范围为0至n – 1

• req：= A [i] – A [j]

• 当A [i] – A [j] <A [j]并且m具有（A [i] – A [j]）时，

• 否则dp [i，j]：= dp [i，j]和2的最大值

• ret：= ret和dp [i，j]的最大值

• dp [i，j]：= dp [i，j]的最大值，dp [j，m [A [i] – A [j]]] + 1

• m [A [i]]：= i

• 对于范围i – 1中的j，降低到0

• 当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]

输出结果

5