python/TangDou/AcWing/LIS/896_ErFen.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int a[N];
int f[N], idx;

int find(int x) {
    int l = 1, r = idx; //左闭右闭
    while (l < r) {
        int mid = (l + r) >> 1;
        if (f[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

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

    f[++idx] = a[1];

    for (int i = 2; i <= n; i++)
        if (a[i] > f[idx])
            f[++idx] = a[i];
        else {
            int pos = find(a[i]);
            f[pos] = a[i];
        }

    printf("%d\n", idx);
    return 0;
}