Description
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。
Input
第1行:N,N为正整数的数量(3 ≤ N ≤ 10000)。
第2 – N+1行:N个正整数。(2 ≤ A[i] ≤ 10^9)
Output
最长等差数列的长度。
Input 示例
10
1
3
5
6
8
9
10
12
13
14
Output示例
5
思路
$dp[i][k]$ 代表等差数列以 $i,k$ 结尾的段的贡献。
则对于等差的三个数 $j,i,k$ ,显然有 $dp[i][k]=dp[j][i]+1$ ,其中这个 $1$ 即为 $k$ , $dp[j][i]=0$ 时, $dp[i][k]=3$ 。
找出最大值即可。
AC 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
typedef long long LL;
short dp[maxn][maxn];
LL a[maxn],n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
sort(a+1,a+n+1);
short int ans = 2;
for(int i=2; i<=n; i++)
{
int j = i-1,k=i+1;
while(j>0&&k<=n)
{
if(a[j]+a[k]>2*a[i])
--j;
else if(a[j]+a[k]<2*a[i])
++k;
else
{
dp[i][k] = dp[j][i]==0?3:dp[j][i]+1;
ans = max(ans,dp[i][k]);
--j,++k;
}
}
}
cout<<ans<<endl;
return 0;
}