设f[i][j]为：第iii个数字作为等差数列的倒数第二位，第jjj的数字作为等差数列最后一位的 最长等差数列。
必然，当n≥2时必然能够形成大小为2的等差数列
故可得初始化f[ ][ ]=2.我们需要通过动态规划来找出大于等于3的长度的等差数列。
f[i][j]=f[k][i]+1表示以j结尾的等差数列添上第i位。这里保证k<j<i且a[j]+a[k]=2∗a[i]
如果枚举每一个ijk，复杂度O(n^3)，妥妥的超时，所以我们可以优化枚举的状态。
即枚举每一个i，根据第二个约束条件的大小关系逐渐将k向左，j向右扫，并在达到平衡状态时进行转移。这样复杂度O(n^2)。
i的枚举方式，即顺序枚举保证了f[k][i]的存在,即中间数i(k+i)/2<i。
#include <iostream> #include<stdio.h> #include<bits/stdc++.h> using namespace std; const int maxn=10005; int n; int a[maxn]; short int ans=2; short int f[maxn][maxn]; int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a,a+n); for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) f[i][j]=2; sort(a+1,a+n+1); for (int i=2;i<n;++i) { int k=i-1,j=i+1; while (k>=1 && j<=n) { if (a[k]+a[j]<2*a[i]) j++; else if (a[k]+a[j]>2*a[i]) k--; else f[i][j]=f[k][i]+1,ans=max(ans,f[i][j]),k--,j++; } } cout<<ans<<endl; return 0; }
原文：https://www.cnblogs.com/Qing-Jia/p/13509113.html