N个不同的正整数，找出由这些数组成的最长的等差数列。
例如：1 3 5 6 8 9 10 12 13 14
等差子数列包括(仅包括两项的不列举）
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14
其中6 8 10 12 14最长，长度为5。
输入
第1行：N，N为正整数的数量(3 <= N <= 10000)。
第2 - N+1行：N个正整数。(2<= A[i] <= 10^9)
输出
最长等差数列的长度。
输入样例
10
1
3
5
6
8
9
10
12
13
14
输出样例
5
等差序列的规律是 2*a[i]=a[i-1]+a[i+1];
分开看就是 i,j,k
以j为轴，i找左边，k找右边，
确定i,j,k可以组成等差数列的时候
之后的状态转移方程 dp[j][k]=dp[i][j]+1;
k找到的时候 证明 i,j,k可以组成等差序列，所以dp[j][k]=dp[i][j]+1;
比如 1 2 3 4 5 6
dp[1][2]=2;
dp[2][3]=dp[1][2]+1;
dp[3][4]=dp[2][3]+1;
#include <bits/stdc++.h> using namespace std; const int maxn = 10010; short dp[maxn][maxn]; int a[maxn]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } sort (a + 1, a + n + 1); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { dp[i][j] = 2; } } int ans = 2; for (int j = 1; j <= n; j++) { int i = j - 1, k = j + 1; while (i >= 1 && k <= n) { if (a[j] * 2 == a[i] + a[k]) { dp[j][k] = dp[i][j] + 1; ans = max(ans, (int)dp[j][k]); i--; k++; } else if (a[j] * 2 > a[i] + a[k]) { k++; } else { i--; } } } cout << ans << endl; return 0; }
