Arithmetic Progressions

题意
问从数列中取出尽可能多的数字使得这些数字成等差数列

思路
设 $dp\left[i\right]\left[j\right]$dp[i][j]表示以v[i]和v[j]相邻构成的最长数列长度。
$dp\left[i\right]\left[j\right]=max\left(dp\right[i\left]\right[j],dp[k\left]\right[i]+1)\left(k属于\right[1,i-1\left]\right(当且仅当2\ast a\left[i\right]==a\left[j\right]+a\left[k\right])$dp[i][j]=max(dp[i][j],dp[k][i]+1)(k属于[1,i−1](当且仅当2∗a[i]==a[j]+a[k])
所以我们只需要枚举i的个数，然后向左向右搜索

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int v[5005];
int dp[5005][5005];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &v[i]);
    sort(v + 1, v + n + 1);
    int ans = 2;
    for(int i = 1; i < n; i++){
	for(int j = i + 1; j <= n; j++){
		dp[i][j] = 2;
	}
    }
    for(int i = 1; i < n; i++){
	int j = i + 1, k = i - 1;///j是右指针 k是左指针
	while(j <= n && k >= 1){
		if(v[j] + v[k] == 2 * v[i]){
			dp[i][j] = dp[k][i] + 1;
			ans = max(ans, dp[i][j]);
			j++; k--;
			if(j > n || k < 1) break;
		}
		else if(v[j] + v[k] > 2 * v[i]){
			k--;
			if(j > n || k < 1) break;
		}
		else{
			j++;
			if(j > n || k < 1) break;
		}
	}
    }
    printf("%d\n", ans);
    return 0;
}