题目描述
给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。我们想知道此时最长上升子序列长度是多少？
输入
第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）
输出
1行，表示最长上升子序列的长度是多少。
样例输入
3
0 0 2
样例输出
2
提示
100%的数据 n<=100000
【思路】：
就是用dp表示前i个的最长上升子序列长度，注意一开始赋值成1（坑了我一把，呜呜呜），然后考虑当前点放到序列里不,然后就ok了.
代码：O(N2)
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar(); return x * f; } int a[10080],n,ans,dp[10000]; int main() { cin>>n; for(int i=1; i<=n; ++i) { cin>>a[i]; dp[i]=1; } for(int i=2; i<=n; ++i) { for(int j=1; j<i; ++j) { if(a[i]>a[j]&&dp[j]+1>dp[i]) { dp[i]=dp[j]+1; } } } for(int i=1; i<=n; ++i) { if(dp[i]>ans) { ans=dp[i]; } } cout<<ans; return 0; }
优化代码：O(n*logn)
【思路】：
用二分查找，可是二分很难怎么办？
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字 lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字
竟然可以直接二分，那还怂个P。
更多解释见https://www.cnblogs.com/wxjor/p/5524447.html（和这篇博客学的）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=99999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar(); return x * f; } int a[maxn],d[maxn],n; int len=1; int main() { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); d[1]=a[1]; for(int i=2; i<=n; i++) { if(a[i]>d[len]) d[++len]=a[i]; else { int j=lower_bound(d+1,d+len+1,a[i])-d; d[j]=a[i]; } } printf("%d\n",len); return 0; }
原文：https://www.cnblogs.com/pyyyyyy/p/10770939.html