$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

先看这个题解：戳这里
先回顾一下上个题解的代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[1010], f[1010];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    a[0] = -0x3f3f3f3f;                                   //可能会有负数，所以a[0]要设置为无穷小
    for (int i = 1;i <= n; i++)
        for (int j = 0;j < i; j++)
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);  //如果a数组符合“上升”的条件，就尝试更新f数组
    int ans = 0;
    for (int i = 1;i <= n; i++) ans = max(ans, f[i]);     //取最大值ans
    printf("%d\n", ans);
    return 0;
}

所以这道题就是数据升级了一下……
其实我看这道题就连上面代码中的f都没必要存……
其实就是：（拿样例说吧）

a:  3 1 2 1 8 5 6
    ^
f:  3


a:  3 1 2 1 8 5 6
      ^
f:  1


a:  3 1 2 1 8 5 6
        ^
f:  1 2


a:  3 1 2 1 8 5 6
          ^
f:  1 2


a:  3 1 2 1 8 5 6
            ^
f:  1 2 8


a:  3 1 2 1 8 5 6
              ^
f:  1 2 5


a:  3 1 2 1 8 5 6
                ^
f:  1 2 5 6
完成！最后1 2 5 6长度（ans）为4，所以……懂了吧？

奉上AC代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[100010], s[100010], top = 0;
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    a[0] = -0x3f3f3f3f;
    s[++top] = a[1];
    for (int i = 2;i <= n; i++) {
        if(a[i] > s[top]) s[++top] = a[i];
        else *lower_bound(s + 1, s + 1 + top, a[i]) = a[i];
    }
    printf("%d\n", top);
    return 0;
}