给出N个正整数，要求选出一些数组成等差数列。
问最长的等差数列的长度是多少。
3 <= N <= 10000 2<= Ai <= 1e9
容易想到用DP的方法。
dp[i][j]表示以j为中间的项拓展的最大的等差数列长度。
因此可以用双指针拓展，复杂度N*N。这里用short存储可以避免MLE
#pragma warning(disable:4996) #include<iostream> #include<algorithm> #include<bitset> #include<tuple> #include<unordered_map> #include<fstream> #include<iomanip> #include<string> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<list> #include<queue> #include<stack> #include<sstream> #include<cstdio> #include<ctime> #include<cstdlib> #define INF 0x3f3f3f3f #define inf 0x7FFFFFFF #define MOD 998244353 #define moD 1000000003 #define pii pair<int,string> #define eps 1e-8 #define equals(a,b) (fabs(a-b)<eps) #define bug puts("bug") #define re register #define fi first #define se second const int maxn = 1e4 + 5; const double Inf = 10000.0; const double PI = acos(-1.0); typedef long long ll; typedef unsigned long long ull; using namespace std; short dp[maxn][maxn]; int a[maxn]; int main() { int n; short res = 2; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", a + i); sort(a, a + n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { dp[i][j] = 2; } } for (int j = n - 2; j >= 1; j--) { int i = j - 1, k = j + 1; while (i >= 0 && k < n) { if (a[i] + a[k] < (a[j] << 1)) k++; else if (a[i] + a[k] > (a[j] << 1)) i--; else { dp[i][j] = dp[j][k] + 1; res = max(res, dp[i][j]); i--, k++; } } } printf("%d", res); }