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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个序列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

    以上是 C ++中最长斐波那契子序列的长度 的全部内容， 来源链接： utcz.com/z/322078.html

    回到顶部