LIS最长上升子序列三种方法（模板）

 1 O(n^2)的方法：
 2 #include <iostream>
 3 #include <stdio.h>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 int a[15010],dp[15010],front[15010];
 8 int n;
 9 int main()
10 {
11     scanf("%d",&n);
12     int maxn=0;
13     for(int i=1;i<=n;i++){
14         scanf("%d",&a[i]);
15         dp[i]=1;
16         front[i]=-1;
17         for(int j=1;j<i;j++){
18             if(a[j]<a[i]){
19                 dp[i]=max(dp[i],dp[j]+1);
20                 front[i]=j;
21             }
22         }
23         maxn=max(maxn,dp[i]);
24     }
25     cout<<maxn<<endl;
26     return 0;
27 }
28 O(n log n)的方法：
29 二分：
30 #include <iostream>
31 #include <stdio.h>
32 #include <cstring>
33 #include <algorithm>
34 using namespace std;
35 int n,a[20010],c[20010],len=0;
36 int Find(int x)
37 {
38     int l=1,r=len,mid;
39     while(l<=r){
40         mid=(l+r)>>1;
41         if(x>c[mid]){ //记忆方法:求上升序列，就表示x更大，那么就是大于
42             l=mid+1;
43         }else r=mid-1;
44     }
45     return l;
46 }
47 int main()
48 {
49     scanf("%d",&n);
50     for(int i=1;i<=n;i++)
51         scanf("%d",&a[i]);
52     for(int i=1;i<=n;i++){
53         int k=Find(a[i]);
54         c[k]=a[i];
55         len=max(len,k);
56     }
57     printf("%d",len);
58     return 0;
59 }
60 STL 求最长上升子序列：
61 #include <iostream>
62 #include <stdio.h>
63 #include <algorithm>
64 #include <cstring>
65 using namespace std;
66 #define N 1000
67 #define INF 2^32-1
68 int n;
69 int a[N],dp[N];
70 void solve()
71 {
72     fill(dp,dp+n,INF);
73     for(int i=0;i<n;i++)
74         *lower_bound(dp,dp+n,a[i])=a[i];
75     printf("%d
",lower_bound(dp,dp+n,INF)-dp);
76 }
77 int main()
78 {
79     while(cin>>n){
80         for(int i=0;i<n;i++)
81             cin>>a[i];
82         solve();
83     }
84     return 0;
85 }
LIS最长上升子序列三种方法 （模板）

LIS最长上升子序列三种方法（模板）
