给定数组a与长度n，
问数组的最长严格单调上升子序列

eg. 2 4 6 8 10 12 14 16 13 14 15

2 ans = 1
2 4 ans = 2
2 4 6 ans = 3
2 4 6 8 ans = 4
2 4 6 8 10 ans = 5
2 4 6 8 10 12 ans = 6
2 4 6 8 10 12 14 ans = 7
2 4 6 8 10 12 14 16 ans = 8
2 4 6 8 10 12 13 16 ans = 8
2 4 6 8 10 12 13 14 ans = 8
2 4 6 8 10 12 13 14 15 ans = 9

做法
1.维护d数组，首先d[1]=a[1]
2.若a[i]>d[len]，则将a[i]插入d中，d[++len]=a[i]
3.若a[i]<=d[len]，则在d中找到第一个大于a[i]的位置pos，将d[pos]替换为a[i]

正确性证明
容易发现d数组单调性具有保障。
若a[i]>d[len]，
那么ans一定会被更新为len+1，
又由d数组的单调性，
知道ans在没有出现x>d[len+1]时不会更新。
若a[i]<=d[len]，
那么找到第一个大于a[i]的数字，
即pos=lower_bound(d+1,d+len+1,a[i])，
此时我们将这个数字换为a[i]，
因为作比较时只跟d[len]作比较。
所以在替换时不影响答案。
若d[len]被替换，
则说明上一个d[len]到a[i]中不存在比d[len]更大的数，
d[len]变得更小，对放置之后的数字会更优，
所以每次替换不会变成一个更劣的情况。
同样的，替换d[1~len-1]之中的数，
是一个更新换代的过程，
答案会变得更优（不变优下至少不会变劣）。
既然每一次操作不会更劣，
能更优就更优，
那么全部做完之后得到的一定是最优解。

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

const int N = 100010;
int a[N], n, d[N];

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

    d[1] = a[1];
    int len = 1;

    for (int i = 2; i <= n; i++) {
        if (a[i] > d[len]) d[++len] = a[i];
        else {
            int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
            d[pos] = a[i];
        }
    }

    cout << len << endl;

    return 0;
}

算法的时间复杂度为$O(n\log n)$