https://leetcode-cn.com/problems/longest-arithmetic-sequence/
本题需要采用动态规划的方法，使用一个map数组记录以某个数为结尾的所有可能的等差数列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
int len = A.size();
if(len == 0) return 0;
vector<map<int, int>> record(len);
int max_len = 0;
for(int i=0; i<len; ++i) {
for(int j=0; j<i; ++j) {
int diff = A[i]-A[j];
if(record[j].find(diff) == record[j].end()) record[i][diff] = 2;
else record[i][diff] = record[j][diff]+1;
if(record[i][diff] > max_len) max_len = record[i][diff];
}
}
return max_len;
}
};
|