等差数列

等差数列

题目大意

分析

考虑 $dp[i][j]$ 表示等差数列中最后两项的位置为 $i,j$ ,其最长长度

根据等差数列的性质

假设 $a[L],a[i], a[R]$为等差数列的三项，那么满足

$a[L] + a[R] = 2 * a[i]$

故可以枚举 $i$, 向 $i$ 的 左右两边扫找到满足条件的 $L,R$

由于原数组位置可变，排序后单调，可用双指针扫

Code

short int f[10005][10005];
int a[10005];

// 卡int  shabi
signed main()
{
    int n;cin >>n ;
    for(int i = 1;i <= n;i++) cin >> a[i];

    sort(a+1,a+1+n);
    short int res = 0;

    for(int i = 1;i <= n;i++)for(int j = i+1;j<=n;j++) f[i][j] = 2;
    for(int i = 2;i <= n-1;i++){
        int l = i-1,r = i+1;
        while(l >= 1 && r <=n){
            if(a[l] + a[r] > 2*a[i]) {
                l--;
            }
            else if(a[l]+a[r] < 2*a[i] ){
                r++;
            } 
            else{
                short int t = f[l][i] + 1;
                f[i][r] = max(t,f[i][r]);
                res = max(res,f[i][r]);
                l--; // l 和 r 不能一起动,为什么不清楚ing
            }
        }
    }
    cout << res << endl;
    return 0;
}