二分查找部分非常灵活，这里直接使用STL自带的二分查找算法。

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int len = 0;
    for (int i = 0; i < n; i++)
    {
        int  pos = len;
        pos = lower_bound(q + 1, q + len + 1, a[i]) - (q + 1);
        len = max(len, pos + 1);
        q[pos + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}

关于此题的二分查找，参考一下@well188的评论：
二分就是太灵活了，太容易出错了，想不出错就得像STL那样，范围永远：“左闭右开”，检查条件永远：“大于等于或大于”。不得不承认，有时候加上限制反而更敏捷。

int len=0;
q[0]=-1e9;//因为有负值，第0个数还是要设一个最小值
for(int i=0;i<n;i++){
    int l=0,r=len+1;//左闭右开
    while(l<r){
        int mid=l+r>>1;
        if(q[mid]>=a[i]) r=mid;
        else l=mid+1;
    }
    len=max(len,l);//这里r和l都可以，因为左闭右开保证能进入while循环
    q[l]=a[i];
}
printf("%d\n",len);

作者：well188
链接：https://www.acwing.com/activity/content/code/content/62458/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。