最长上升子序列(lis)

本解法时间复杂度$O(nlogn)$，还有一种 DP 的 $O(n^2)$ 的求法，感兴趣的可以上网了解一下

#include<cstdio>
#include<algorithm>
using namespace std;
#define re register
const int MAXn = 1e5;

template <class T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c >'9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}

int n, s[MAXn + 10], cnt;
int main() {
    read(n);
    for (re int i = 1, a; i <= n; ++i) {
        read(a);
        if (a > s[cnt]) {
            s[++cnt] = a;
        } else {
            *lower_bound(s + 1, s + 1 + cnt, a) = a;
        }
    }
    printf("%d\n", cnt);
}