嗯，题解以及不好理解的地方都已放入注释中，欢迎查看

参考代码：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;

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

// 时间复杂度：O(nlogn)

// q[i]：表示最大上升子序列长度为i的最小值
// 对于3 1 2 1 8 5 6
// 长度为1的有3 1（以前两个为例）
// 对于2来说，要从之前的两者中选择，如果能选更小的就不需要选则较大的，对于2来说选择更小的1会得到的长度一定会比选择较大的3得到的长度长
// 所以有1在3就不会被用到

// 使用q[i]表示长度为i的最小值，例如本例（q[1] = 1而不是3），我们猜想q[i]随着长度i的增加，q[i]保存的最小值也是严格单调递增的
// 反证：假设a = q[5] >= q[6] = b 那么对于q[6]来说，长度为6的数的上一个数（即对应长度为5的数c是一定小于b, 即 c < b <= a, 即 c < a）,则对于q[5]的a来说，有更小的c比a小，则与q[5]保存的最小值a矛盾，由此得证，该q序列一定是严格单调递增的

// 所以对于a[i]我们只要从q数组中通过二分找到比a[i]小的最大的数q[r]，长度len为r + 1,此时更新q[r + 1]为更小的值a[i]，（因为q数组要保存当前长度的最小值，那么当前长度r + 1被更新，则说明当前值已不是最小，已经被a[i]所替代）

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int len = 0;
    for(int i = 0; i < n; i++){
        // 对于l为什么从0开始，极端情况下，如果a[i]为最小值，是要更新q[1]的，也就是对于当前位置a[i]之前的数产生的q数组不是定值会随着a数组的遍历而进行更新，由于q[1]也有可能被更新，则r应该要能二分到0的位置才能使得q[r + 1]为q[1]
        int l = 0, r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        // 更新最大子序列长度len
        len = max(len, r + 1);
        // a[i]为更小值
        // q[r] 为小于a[i]的最后一个数，q[r + 1] 一定大于等于 a[i]，所以将 q[r + 1] 更新为当前长度的最小值 
        q[r + 1] = a[i];
    }
    cout << len << endl;
    return 0;
}