C++ 中最长算术序列

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

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

  • 创建一个映射 dp，n := A 的大小，设置 ret := 2

  • 对于 i 的范围从 0 到 n – 1

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

      • diff := A[j] – A[i]

      • dp[i, diff] := 1 + dp[j, diff]

      • ret := 1 + dp[i, diff] 和 ret 的最大值

  • 返回 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

更新于: 2020-04-30

281 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告