题目描述 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
这题暴力直接水过,一开始有个数据卡主了,第一个点没过去,原来是在输入一个数据的时候,用flag标记下就可以了。
# include<cstdio> # include<iostream> # include<algorithm> # include<cstring> using namespace std; # define MAX 233 int a[MAX]; int cnt; int n; void dfs( int k,int num ) { if ( k==n+1 ) { return; } for ( int i = k+1;i <= n;i++ ) { if ( a[i]-a[k]==num ) { cnt++; dfs(i,num); } } } int main(void) { while ( cin>>n ) { int ans = 0; int flag=0; memset(a,0,sizeof(a)); for ( int i = 1;i <= n;i++ ) { cin>>a[i]; } if ( n==1 ) { flag =1; } if ( flag ) cout<<"1"<<endl; else { sort(a+1,a+1+n); for ( int i = 1;i <= n-1;i++ ) { for ( int j = i+1;j <= n;j++ ) { cnt = 1; dfs(i,a[j]-a[i]); ans = max(ans,cnt); } } cout<<ans<<endl; } } return 0; }