C ++中最长的算术序列

假设我们有一个整数数组A，我们必须返回A中最长的算术子序列的长度。您知道A的子序列是列表A [i_1]，A [i_2]，...，A [ i_k]的值为0 <= i_1 <i_2 <... <i_k <= A.length-1，并且当B [i + 1]-B [i]都是相同的值（对于0时，序列B是算术的） <= i <B.length-1）。因此，如果输入类似于[9,4,7,2,10]，则输出将为3。最长的子序列为[4,7,10]。

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

• 制作映射dp，n：= A的大小，设置ret：= 2

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

• 差异：= A [j] – A [i]

• dp [i，diff]：= 1 + dp [j，diff]

• ret：= 1 + dp [i，diff]的最大值，然后ret

• 对于0到i – 1范围内的j

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestArithSeqLength(vector<int>& A) {
      unordered_map <int, unordered_map <int, int> > dp;
      int n = A.size();
      int ret = 2;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < i; j++){
            int diff = A[j] - A[i];
            dp[i][diff] = 1 + dp[j][diff];
            ret = max(1 + dp[i][diff], ret);
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {9,4,7,2,10};
   Solution ob;
   cout << (ob.longestArithSeqLength(v1));
}

输入值

[9,4,7,2,10]

输出结果

3