题目描述
由n个整数组成的数列，记为b[1], b[2], …, b[n]。若存在i1<i2<i3< … < ie 且有b[i1]< b[i2]< … <b[ie]则称为长度为e的上升子序列。求最长上升子序列(Longest increasing subsequence, LIS)
输入输出格式
输入格式
一行，整数序列. 序列长度<=100000, 每个整数绝对值<=10000
输出格式
最大上升子序列长度
输入输出样例
样例数据
输入数据
2 1 1 2 3
输出数据
3
标签
二分查找
AC代码
#include <bits/stdc++.h>
using namespace std;
int n=0,x[200000],tail[200000]={0},cnt;
void print(){
cout<<"============"<<endl;
for(int k=0;k<cnt;k++){
cout<<tail[k]<<' ';
}
cout<<endl;
}
int main()
{
//freopen("lis.in","r",stdin);
//freopen("lis.out","w",stdout);
while(cin>>x[n])n++;
tail[0]=x[0];
cnt=1;
for(int i=1;i<n;i++){
if(x[i]>tail[cnt-1]){
tail[cnt]=x[i];
cnt++;//当找到一个符合条件的数时计数器cnt+1;
//print();
continue;
}
//d[cnt]=x[i];
int l=lower_bound(tail,tail+cnt,x[i])-tail;
// cout<<"l:"<<l<<endl;
tail[l]=x[i];
// print();
}
cout<<cnt;
return 0;
}
