python/TangDou/AcWing/LIS/896.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;

int n, a[N];

// 数组模拟栈
int f[N], fl;

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

    // 1、首个元素入栈
    f[0] = a[0];

    // 2、后续元素开始计算
    for (int i = 1; i < n; i++) {
        if (a[i] > f[fl])
            f[++fl] = a[i];
        else
            // 利用STL的二分，在f中查找第一个大于等于a[i]的值，并完成替换
            *lower_bound(f, f + fl, a[i]) = a[i];
    }
    // 栈内元素数量就是答案
    printf("%d\n", fl + 1);
    return 0;
}