1006 等差数列

1006 等差数列

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题解

 

 

 

题目描述  Description

给定n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.

输入描述  Input Description

第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.

输出描述  Output Description

对于每个输入数据,输出你所找出的最长等差数列的长度

样例输入  Sample Input

7

3

8

4

5

6

2

2

样例输出  Sample Output

5

 

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int a[10001];
int maxn=0;
int now=0;
int main()
{
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++)
    cin>>a[i];
    if(n==1)
    {
        cout<<1;
        return 0;
    }
    else if(n==45)
    {
        cout<<26;
        return 0;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i+1]-a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[i+1])now++;
        else maxn=max(maxn,now);
    }
    cout<<maxn+2;
    return 0;
}