数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律C++ 中最长算术序列
假设我们有一个整数数组 A，我们需要返回 A 中最长算术子序列的长度。众所周知，A 的子序列是 A[i_1]、A[i_2]、...、A[i_k] 的列表，其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1，并且序列 B 当 B[i+1] - B[i] 全部具有相同的值时（对于 0 <= i < B.length - 1）为算术序列。因此，如果输入类似于 [9,4,7,2,10]，则输出将为 3。因为最长的子序列是 [4,7,10]。
为了解决这个问题，我们将遵循以下步骤 -
创建一个映射 dp，n := A 的大小，设置 ret := 2
对于 i 的范围从 0 到 n – 1
对于 j 的范围从 0 到 i – 1
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
更新于: 2020-04-30
281 次浏览
广告