题目描述
给定一个序列，初始为空。现在我们将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 = , f = ;
while(c < '' || c > '') {
if(c == '-') f = -;
c = getchar();
}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int a[],n,ans,dp[]; int main() {
cin>>n;
for(int i=; i<=n; ++i) {
cin>>a[i];
dp[i]=;
}
for(int i=; i<=n; ++i) {
for(int j=; j<i; ++j) {
if(a[i]>a[j]&&dp[j]+>dp[i]) {
dp[i]=dp[j]+;
}
}
}
for(int i=; i<=n; ++i) {
if(dp[i]>ans) {
ans=dp[i];
}
}
cout<<ans;
return ;
}
优化代码：O(n*logn)
【思路】：
用二分查找，可是二分很难怎么办？
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字 upper_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=;
inline int read() {
char c = getchar();
int x = , f = ;
while(c < '' || c > '') {
if(c == '-') f = -;
c = getchar();
}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int a[maxn],d[maxn],n;
int len=;
int main() {
scanf("%d",&n);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
d[]=a[];
for(int i=; i<=n; i++) {
if(a[i]>d[len])
d[++len]=a[i];
else {
int j=lower_bound(d+,d+len+,a[i])-d;
d[j]=a[i];
}
}
printf("%d\n",len);
return ;
}