POJ 2533 Longest Ordered Subsequence

题目描述：LIS（Longest Increasing Subsequence）模板题

分析：O(n^2)的方法

状态表示：d[i]表示以i结尾的最长上升子序列长度

转移方程：d[i]=max{ 1,d(j)+1 } ( j=1,2,3,...,i-1且A[j]<A[i] )

即A[j]<A[i]，d[i]=d[j]+1

A[j]>=A[i],d[i]=1

 1 #include<cstdio>
 2 int main()
 3 {
 4     int N,a[10005],d[10005];
 5     scanf("%d",&N);
 6     for(int i=0;i<N;i++)
 7     scanf("%d",&a[i]);
 8     int max=0;
 9     for(int i=0;i<N;i++)
10     {
11         d[i]=1;
12         for(int j=0;j<i;j++)
13         {
14             if(a[j]<a[i]&&d[j]+1>d[i])
15             d[i]=d[j]+1;
16         }
17         if(d[i]>max)  max=d[i];
18     }
19     printf("%d
",max);
20     return 0;
21 }

O(nlogn)的方法：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int INF=1000000000;
 5 int N,a[10005],d[10005],g[10005];
 6 int main()
 7 {
 8     scanf("%d",&N);
 9     for(int i=0;i<N;i++)
10     scanf("%d",&a[i]);
11     for(int i=1;i<=N;i++) g[i]=INF;
12     int ans=0;
13     for(int i=0;i<N;i++)
14     {
15         int k=lower_bound(g+1,g+1+N,a[i])-g;
16         d[i]=k;
17         g[k]=a[i];
18         ans=max(ans,d[i]);
19     }
20     printf("%d
",ans);
21     return 0;
22 }