优化思路

思路上大体跟闫总的一样,但是对代码进行了改动(是因为我不会手写二分吗,当然不是🤓)

概括的总结为 :
维护一个q数组,保存从a中找出的单调上升的序列,每次遇到递减的,在q中找到大于等于这个数字的最小值,然后把他替换掉

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N = 1e5 + 10;

int a[N], q[N];

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)scanf("%d", &a[i]);

    int idx = 1;
    q[0] = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > q[idx - 1])q[idx++] = a[i];
        else {
            //找在q中大于等于a[i]的最小值 
            int tmp = lower_bound(q, q + idx, a[i]) - q;
            q[tmp] = a[i];
        }
    }
    printf("%d",idx);
    return 0;
}