题目描述

给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N
第二行包含 N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，−109≤数列中的数≤109

样例

输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

算法

（1）上升序列结尾的那个值越小越好，例如：上升序列长度为1时，选1作为上升序列的结尾一定比a[0]=3要好，因为比如后面的那个2，1就可以与他构成，但是3就不可以，意思就是上升序列的结尾越小可以往这个已经构造的序列中插入数的可能更大。
（2）随着序列的增加，最小的结尾数也会随之增加，很好理解可以用反证法，这就为我们后面遍历的时候提供了思路。
（3）下面解决改如何把这个最长的上升的子序列构造出来：
a[N]:存储我们题目要求的序列
q[N]:存储长度为i的上升子序列的结尾的最小值
*我们遍历数组a，对于每一个a[i]我们需要找到q[i]中不大于他的最后一个数（他一定会小于它后面的数，这就不用多说）若我们把a[i]插入这个数的后面，那么上升子序列的长度会+1，也就是q[i+1]的值。
代码中也会有对这个思想更加详细的解释。

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;

int a[N];//保存最整数序列
int q[N];//q[i]保存长度为i的最长上升子序列的结尾元素的最小值
int n;

int main(){
    //输入数据
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    int len=0;
    q[0]=-2e9;
    //二分进行处理
    for(int i=0;i<n;i++){
        int l=-1,r=len+1;//想象成那个上升的坐标，对存在于坐标中的值进行二分
        while(l+1<r){
            int mid=(l+r)/2;
            if(q[mid]<a[i]) l=mid;//l最终的值就是不大于a[i]的最大值
            else r=mid;//r就是它后面的值
        }
        len=max(len,r);
        q[r]=a[i];
    }
    printf("%d\n",len);

}