Arithmetic Progressions

题目链接：Arithmetic Progressions

---

直接令 dp[i][j] 为 a[i] 为序列最后一个数，a[j]为倒数第二个数的最大值。

每次枚举j的时候，找到对应的k，使得a[k]+a[i]=2*a[j]，直接转移即可。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e3+10;
int n,a[N],dp[N][N],res;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			int pos=lower_bound(a+1,a+1+n,2*a[j]-a[i])-a;
			if(a[pos]+a[i]==2*a[j])	dp[i][j]=max(dp[i][j],dp[j][pos]+1);
			res=max(res,dp[i][j]);
		}
	}
	cout<<res+2;
	return 0;
}