C ++中最长的算术序列
假设我们有一个整数数组A，我们必须返回A中最长的算术子序列的长度。您知道A的子序列是列表A[i_1]，A[i_2]，...，A[i_k]的值为0<=i_1<i_2<...<i_k<=A.length-1，并且当B[i+1]-B[i]都是相同的值（对于0时，序列B是算术的）<=i<B.length-1）。因此，如果输入类似于[9,4,7,2,10]，则输出将为3。最长的子序列为[4,7,10]。
为了解决这个问题，我们将遵循以下步骤-
制作映射dp，n：=A的大小，设置ret：=2
对于i，范围为0至n–1
差异：=A[j]–A[i]
dp[i，diff]：=1+dp[j，diff]
ret：=1+dp[i，diff]的最大值，然后ret
对于0到i–1范围内的j
返回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