提供一个比较简单易懂的代码hh

#include<iostream>
using namespace std;
const int N=100010;
int a[N],q[N];
int n,len;

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

    for(int i=1;i<=n;i++)
    {/*遍历a数组,找到a[i]在q数组中相应的位置然后插入,最后q数组长度即len就是答案*/
        int l=0,r=len;
        while(l<r)
        {
            int mid=l+r>>1;
            if(q[mid]<a[i])l=mid+1;
            else r=mid;
        }
        q[r]=a[i];
        if(r==len)len++;
    }


    cout<<len;
    return 0;
}

输入样例：3 1 2 1 8 5 6
过程：
q: 3  ->q: 1 -> q: 1 2-> q: 1 2 ->1 2 8->q: 1 2 5->1 2 5 6