题目大意：给你一个长度为n(2<=n<=5000)的序列，没有重复的数字，序列中每个元素满足(0<=numi<=1e9)。求一个最长的数列满足差分值相同（除n=2外，可以看成等差数列）。输出这个最大长度。
算法梗概：DP。看了几篇博客都说算是个板子套路DP题。在做的时候也想到了DP，但是没找对状态。
另外可以用其他算法来做这道题，后面慢慢补。先给出DP算法的代码和思路。
1 #include<cstdio>
2 #include<algorithm>
3 const int maxn = 5e3 + 5;
4 int dp[maxn][maxn],n,num[maxn];
5 int main()
6 {
7 scanf("%d",&n);
8 for(int i=1;i<=n;++i){
9 scanf("%d",num+i);
10 for(int j=1;j<=n;++j){
11 dp[i][j] = 2;
12 }
13 }
14 std::sort(num+1,num+1+n);
15 int ans = 2;
16 for(int i=1;i<=n-1;++i){
17 int pre = i - 1;
18 for(int j=i+1;j<=n;++j){
19 ///令d=num[j] - num[i],因为序列是递增的，所以num[i] - num[pre]在pre刚开始不满足条件时大于d，在pre刚好满足条件时等于d，继续遍历则小于d，后来的遍历是无意义的所以跳出即可
20 while(pre > 0 && num[j] - num[i] > num[i] - num[pre]) pre--;
21 if(pre==0) break;
22 else if(pre > 0 && num[j] - num[i] == num[i] - num[pre]) dp[i][j] = std::max(dp[i][j],dp[pre][i]+1);
23 ans = std::max(ans,dp[i][j]);
24 }
25 }
26 printf("%d
",ans);
27 return 0;
28 }
DP思路：dp[i][j]表示已下标i，j（i<j）为结尾两个元素的一个子序列的长。枚举i，以i+1开始向后遍历j，这样对于每对i，j我们可以求出他们的差，以这个差为标准，从i-1开始向前遍历记为pre，直到找到的pre和i，j满足num[j] - num[i] == num[i] - num[pre]。如果找到这样的num[pre]更新dp[i][j]即可。
状态转移方程：dp[i][j] = max(dp[i][j],dp[pre][i]+1)
直接用用等差数列的通项公式来暴力
1 #include <cstdio>
2 #include <algorithm>
3 #include <set>
4 using namespace std;
5 const int maxn = 5e3+50;
6 int num[maxn],n;
7 set<int> se;
8 int main()
9 {
10 scanf("%d",&n);
11 for(int i = 1; i<=n; ++i)
12 {
13 scanf("%d",num+i);
14 se.insert(num[i]);
15 }
16 sort(num+1,num+n+1);
17 int ans = 2,d,k;
18 for(int i=1;i<=n;++i)
19 {
20 for(int j=i+1;j<=n;++j)
21 {
22 k = 2,d = num[j] - num[i];
23 if(!se.count(num[i] + ans*d)) continue;
24 while(se.count(num[i] + k*d)) k++;
25 ans = max(ans,k);
26 }
27 if(ans==n) break;
28 }
29 printf("%d
",ans);
30 return 0;
31 }
核心代码：
1 k = 2,d = num[j] - num[i];
2 if(!se.count(num[i] + ans*d)) continue;
3 while(se.count(num[i] + k*d)) k++;
4 ans = max(ans,k);
暴力思路：ak = a1 + (k-1)d;
两层for循环来枚举a1和d，对于每对<a1,d>,枚举k来得到一个ak，判断ak是不是存在在序列中，存在继续枚举，否则更新答案。
请注意！！！ if(!se.count(num[i] + ans*d)) continue; 这行代码的作用，对于你已经更新到的答案ans，如果num[i] + ans*d都不存在，那么无法更新答案，所以跳过这层循环。
没有这行代码会TLE在test 57或者test 58，做题就死在了这里了。
还有些同学用了二分函数，其实和暴力的核心思想差不多，用二分函数优化很多，这里只给代码，不解释了如果暴力看懂了这个也就懂了
1 #include<cstdio>
2 #include<algorithm>
3 const int maxn = 5e3 + 5;
4 int dp[maxn][maxn],n,num[maxn];
5 int main()
6 {
7 scanf("%d",&n);
8 for(int i=1;i<=n;++i) scanf("%d",num+i);
9 std::sort(num+1,num+1+n);
10
11 int ans = 2,res,d,pos;
12 for(int i=1;i<=n-1;++i){
13 for(int j=i+1;j<=n;++j){
14 d = num[j] - num[i];
15 res = 2;
16 pos = std::lower_bound(num+j+1,num+n+1,num[i]+ans*d) - num;
17 if(num[pos]!=num[i]+ans*d) continue;
18 for(int k=j;k<=n-1;){
19 pos = std::lower_bound(num+k+1,num+n+1,num[k]+d) - num;
20 if(num[pos]==num[k]+d){
21 k = pos;
22 res++;
23 }
24 else break;
25 }
26 ans = std::max(ans,res);
27 }
28 }
29 printf("%d
",ans);
30 return 0;
31 }
This’s all！如有错误，请评论指正谢谢！！