51nod 1055 最长等差数列

51nod 1055 最长等差数列

Description

N个不同的正整数，找出由这些数组成的最长的等差数列。例如：1 3 5 6 8 9 10 12 13 14等差子数列包括(仅包括两项的不列举）1 3 51 5 9 133 6 9 123 8 135 9 136 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 示例

1013568910121314

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 代码

#includeusing 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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。