首页 > 代码库 > 1055 最长等差数列

1055 最长等差数列

2024-08-12 15:56:28   219人阅读

1055 最长等差数列
基准时间限制：2 秒 空间限制：262144 KB 
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示例
1013568910121314
Output示例
5
 1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<iostream> 4 #include<queue> 5 #include<math.h> 6 #include<string.h> 7 #include<algorithm> 8 using namespace std; 9 typedef long long LL;10 short int dp[10005][10005];11 LL ans[10005];12 using namespace std;13 int main(void)14 {15     int i,j;16     for(i = 0; i <= 10000; i++)17     {18         fill(dp[i],dp[i]+10001,2);19     }20     int n;21     scanf("%d",&n);22     for(i = 1; i <= n; i++)23     {24         scanf("%lld",&ans[i]);25     }26     sort(ans+1,ans+n+1);27     int l ,r;short int an = 2;//printf("%d\n",n);28     for(i = n-1; i >= 1 ; i--)29     {30        l = i-1;r = i+1;31        while(l >= 1&&r <= n)32        {33            if(ans[l] + ans[r] ==(LL)2*ans[i])34            {35                dp[l][i] = dp[i][r] + 1;36                an = max(an,dp[l][i]);37                l--;38            }39            else if(ans[l] + ans[r] < (LL)2*ans[i])40            {41                r++;42            }43            else l--;44            //printf("%d\n",dp[l][i]);45        }46     }47     printf("%d\n",an);48     return 0;49 }

 

1055 最长等差数列


联系
我们