poj 2533 Longest Ordered Subsequence 最长递增子序列(LIS)

两种算法

1. O(n^2)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int a[1005];
 7 int dp[1005];
 8 int main()
 9 {
10     int n, maxn;
11     while(scanf("%d", &n) != EOF)
12     {
13         maxn = 0;
14         for(int i = 0; i < n; i++)
15         {
16             scanf("%d", &a[i]);
17             dp[i] = 1;
18             for(int j = 0; j < i; j++)
19             {
20                 if(a[j] < a[i] && dp[j] + 1 > dp[i])
21                     dp[i] = dp[j] + 1;
22             }
23         }
24         for(int i=0;i<n;i++)
25         {
26             if(maxn < dp[i])
27                     maxn = dp[i];
28         }
29         printf("%d
", maxn);
30     }
31     return 0;
32 }

View Code

2.O(nlog(n))

O(nlogn)的算法关键是它建立了一个数组c[]，c[i]表示长度为i的不下降序列中结尾元素的最小值，用K表示数组目前的长度，算法完成后K的值即为最长不下降子序列的长度。

具体点来讲：

设当前的以求出的长度为K，则判断a[i]和c[k]：

1.如果a[i]>=c[k]，即a[i]大于长度为K的序列中的最后一个元素，这样就可以使序列的长度增加1，即K=K+1,然后现在的c[k]=a[i]；

2.如果a[i]<c[k]，那么就在c[1]...c[k]中找到最大的j,使得c[j]<a[i],然后因为c[j]<a[i]，所以a[i]大于长度为j的序列的最后一个元素，那么就可以更新长度为j+1的序列的最后一个元素，即c[j+1]=a[i]。

算法复杂度的分析：

因为共有n个元素要进行计算；每次计算又要查找n次，所以复杂度是O(n^2)，但是，注意到c[]数组里的元素的单调递增的，所以我们可以用二分法，查找变成了logn次。这样算法的复杂度就变成了O(nlogn)。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 using namespace std;
 5 int a[1005],dp[1005],c[1005],n;
 6 
 7 int bin(int size,int k)
 8 {
 9     int l=1,r=size;
10     while(l<=r)
11     {
12         int mid=(l+r)/2;
13         if(k>c[mid]&&k<=c[mid+1])
14             return mid+1;
15         else if(k<c[mid])
16             r=mid-1;
17         else
18             l=mid+1;
19     }
20 
21 }
22 int LIS()
23 {
24     c[1]=a[1];
25     dp[1]=1;
26     int j,ans=1;
27     for(int i=2;i<=n;i++)
28     {
29         if(a[i]<=c[1])
30             j=1;
31         else if(a[i]>c[ans])
32             j=++ans;
33         else
34             j=bin(ans,a[i]);
35         c[j]=a[i];
36         dp[i]=j;
37     }
38     return ans;
39 }
40 int main()
41 {
42     while(scanf("%d",&n)!=EOF)
43     {
44         for(int i=1;i<=n;i++)
45             scanf("%d",&a[i]);
46         printf("%d
",LIS());
47     }
48     return 0;
49 }

View Code