题意
给你 n 个数，让你从中找出最长的等差序列
思路
dp求最长等差数列的长度 dp [ i ] [ j ] :以第 i 个数为倒数第二位，第 j 个数为倒数第一位的等差序列的长度； 转移方程 dp [ i ] [ j ] = dp [ k ] [ i ] + 1; 如果 n > = 2 , 那么等差序列最短长度也是 2 ，所以 dp 初始化可以初始化为 2 .
代码
#include<iostream>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131
#define INF 0x3f3f3f3f
#define P pair<int,int>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
const double eps
=1e-7;
const double pai
=acos(-1.0);
const int N
=2e4+10;
const int maxn
=4e5+10;
const int mod
=1e9+7;
int dp
[5010][5010];
int n
,a
[5010];
int main(){
scanf("%d",&n
);
for(int i
=0;i
<n
;i
++) scanf("%d",&a
[i
]);
sort(a
,a
+n
);
for(int i
=0;i
<n
-1;i
++)
{
for(int j
=i
+1;j
<n
;j
++)
{
dp
[i
][j
]=2;
}
}
int maxx
=2;
for(int i
=1;i
<n
-1;i
++)
{
int j
=i
+1,k
=i
-1;
while(k
>=0&&j
<n
)
{
if(a
[j
]-a
[i
]==a
[i
]-a
[k
])
{
dp
[i
][j
]=dp
[k
][i
]+1;
if(dp
[i
][j
]>maxx
) maxx
=dp
[i
][j
];
k
--,j
++;
}
else if(a
[j
]-a
[i
]<a
[i
]-a
[k
]) j
++;
else k
--;
}
}
printf("%d",maxx
);
return 0;
}
