LIS最长上升子序列模板

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

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int MAXN=1000005;
 6 
 7 int n;
 8 int s[MAXN],f[MAXN];
 9 
10 int find(int x,int r)
11 {
12     int left=1,right=r,mid;
13     while(left<right)
14     {
15         mid=(left+right)>>1;
16         if(f[mid]>s[x]) right=mid;
17         else left=mid+1;
18     }
19     return right;
20 }
21 
22 int LIS(int x)
23 {
24     f[1]=s[x];
25     int len=1;
26     for(int i=2;i<=n;i++)
27     {
28         if(s[i]>f[len])
29             f[++len]=s[i];
30         else
31             f[find(i,len)]=s[i];
32     }
33     return len;
34 }
35 
36 int main()
37 {
38     scanf("%d",&n);
39     for(int i=1;i<=n;i++)
40         scanf("%d",&s[i]);
41     printf("%d
",LIS(1));
42     return 0;
43 }