编程练习-2022-06-10-Andy

题目描述

由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;
}