C++での最長の等差数列

整数の配列Aがあるとすると、Aの最長の算術サブシーケンスの長さを返す必要があります。AのサブシーケンスはリストA [i_1]、A [i_2]、...、A[です。 i_k] with 0 <=i_1

これを解決するには、次の手順に従います-

• マップを作成しますdp、n：=Aのサイズ、設定ret：=2

• 0からn–1の範囲のiの場合

  • 0からi–1の範囲のjの場合

    • 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