C++で与えられた違いの最長の算術部分列

整数配列arrと整数の差があるとすると、arrの最長のサブシーケンスの長さを見つける必要があります。これは、サブシーケンス内の隣接する要素間の差が等差数列になるようなものです。違いと同じです。したがって、入力が[1,5,7,8,5,3,4,2,1]のようで、差が-2の場合、最長の等差数列は[7,5、 3,1]

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

• マップを定義するm
• n：=配列arrのサイズ、ans：=0を設定
• 0からn–1の範囲のiの場合
  • x：=arr [i]
  • m [x]：=1 + m [x --d]
  • ans：=maxofおよびm[x]
• 回答を返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestSubsequence(vector<int>& arr, int d) {
      int n = arr.size();
      map <int,int> m;
      int ans = 0;
      for(int i =0;i<n;i++){
         int x = arr[i];
         m[x] = 1 + (m[x-d]);
         ans = max(ans,m[x]);
      }
      return ans;
   }
};
main(){
   vector<int> v1 = {1,5,7,8,5,3,4,2,1};
   Solution ob;
   cout <<ob.longestSubsequence(v1, -2);
}

入力

[1,5,7,8,5,3,4,2,1]
-2

出力

4