鉴于差异最长算术子序列在C ++

假设我们有一个整数数组ARR和整数差，我们必须找到在ARR的最长子序列，其是算术序列，使得在子序列相邻元件之间的差是一样的差的长度。因此，如果输入像[1,5,7,8,5,3,4,2,1]且差为-2，则输出将为− 4，因为最长的算术序列为[7,5， 3,1]

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

• 定义映射m

• n：=数组arr的大小，设置ans：= 0

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

• x：= arr [i]

• M [X]：= 1 + M [X  -  d]

• ANS：=最大的，且m [X]

• 返回ans

示例

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

#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