鉴于差异最长算术子序列在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