等差数列

题目描述

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

输入要求

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

输出要求

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

假如输入

7
3
8
4
5
6
2
2

应当输出

5

分析:枚举法,n^3时间复杂度,另一种方法是dp,dp[j][i]表示以a[j]和a[i]结尾的最长等差数列的长度。枚举最后两个元素,对于每一个a[j]和a[i],都要找到a[p],p < j,满足a[p] + a[i] == 2 * a[j]。然后dp[p][j] + 1去更新dp[j][i]。看起来是三层循环,但其实对于同一个i,p的位置是随着j增大而增大的,所以最里面的while循环对于每个i值最多是O(n)的代价。总的代价还是O(n^2)。

枚举代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<algorithm>
#include<vector>
#include<cctype>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int i,j,k,d,n,arr[401],ans=0,sum,la;
cin>>n;
if (n<=2)
cout<<n<<endl;
else
{
for(i=0;i<n;i++)
cin>>arr[i];
sort(arr,arr+n);
for (i=0;i<n-1;++i)
{
for (j=i+1;j<n;++j)
{
d=arr[j]-arr[i];
la=j;
sum=2;
for (k=j+1;k<n;++k)
{
if (arr[k]-arr[la]==d)
{
la=k;
++sum;
}
else if(arr[k]-arr[la]>d)
break;
}
if (sum>ans)
ans=sum;
}
cout<<ans<<endl;
}
}
}

dp代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<vector>
#include<cctype>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXL 410
int dp[MAXL][MAXL];
int find_(int a[], int n)
{        
        int i, j;
        for(i = 1; i < n; i++) {
                int p = 0;
                for(j = 0; j < i; j++) {
                        dp[j][i] = 2;
                        while(p < j && a[p] + a[i] < 2 * a[j])
                                p++;
                        if(p < j && a[p] + a[i] == 2 * a[j])
                                dp[j][i] = max(dp[j][i], dp[p][j] + 1);
                }
        }
        int ans = (n > 0);
        for(i = 1; i < n; i++)
                for(j = 0; j < i; j++)
                        ans = max(ans, dp[j][i]);
        return ans;

}
void solve();
int main()
{
    solve();
    return 0;
}
void solve()
{   
    int i,n,arr[401];
    cin>>n;
    for(i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    cout<<find_(arr,n);
}

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。