基准时间限制：2 秒 空间限制：262144 KB 分值: 80 难度：5级算法题
N个不同的正整数，找出由这些数组成的最长的等差数列。
例如：1 3 5 6 8 9 10 12 13 14
等差子数列包括(仅包括两项的不列举）
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14
其中6 8 10 12 14最长，长度为5。
Input
第1行：N，N为正整数的数量(3 <= N <= 10000)。
第2 - N+1行：N个正整数。(2<= A[i] <= 10^9)
Output
最长等差数列的长度。
Input示例
10
1
3
5
6
8
9
10
12
13
14
Output示例
5 一开始想的是dp+哈希，复杂度是O(N*N*log(N)),结果T了，后来看题解发现还有这种优化操作。对于等差数列 a[k],a[i],a[j],必然满足a[i]*2==a[k]+a[j],我们可以枚举所有的i，
然后用两个指针前后移动找到符合要求的状态再进行转移，复杂度O(N^2);
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<stack>
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<time.h>
#include<algorithm>
using namespace std;
#define mp make_pair
#define debug puts("debug")
#define LL long long
#define pii pair<int,int>
map<int,int>M;
short f[][];
int a[],N;
int main(){
int n,i,j,k;
cin>>n;
N=n;
for(i=;i<=n;++i) {
scanf("%d",a+i);
}
sort(a+,a++n);
short ans=;
for(i=;i<=n;++i){
int j=i+,k=i-;
while(k>=&&j<=n){
if(a[k]+a[j]<a[i]*) j++;
else if(a[k]+a[j]>a[i]*) k--;
else{
f[i][j]=max(f[i][j],short(max(f[k][i],(short))
+));
ans=max(ans,f[i][j]);
k--;
j++;
}
}
}
cout<<ans<<endl;
return ;
}