题目描述

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

一道思维的dp，似乎是2017香港区域赛的原题。

我们用dp[i][j] 表示第一个数字是a[i]，第二个数字是a[j] 的最长等差数列，这个当然是可以枚举的啦，但是不能暴力枚举，肯定TLE，所以我们需要优化状态，因为很多状态是不需要的，因为枚举i，j之后，有用的信息不多，所以我们可以考虑枚举j，然后双指针扫描即可。

  1. a[i]+a[k] > a[j]*2 ，当前i大了，所以 i - -
  2. a[i]+a[k] < a[j]*2 ，当前k小了，所以k++
  3. a[i]+a[k] = a[j]*2 ，那么当前是可以状态转移的，dp[i][j] = dp[j][k] +1 ，所以我们需要处理后效性，从后往前枚举即可。

然后这道题卡内存了，又因为dp的值不大，所以我们用short int 优化内存。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10;
int n,a[N];
short int dp[N][N],res;
signed main(){
	cin>>n;	for(int i=1;i<=n;i++)	cin>>a[i];	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)	for(int j=i+1;j<=n;j++)	dp[i][j]=2; res=2;
	for(int j=n-1;j>=1;j--){
		int i=j-1,k=j+1;
		while(i>=1&&k<=n){
			if(a[i]+a[k]>a[j]*2)	i--;
			else if(a[i]+a[k]<a[j]*2)	k++;
			else{
				dp[i][j]=dp[j][k]+1; res=max(res,dp[i][j]); i--,k++;
			}
		}
	}
	cout<<res<<endl;
	return 0;
}