题意：

找出$n$个数组成的序列的最长单调递增子序列。

朴素分析：

状态表示： $F[i]$表示从第一个数字开始，以$a[i]$结尾的最长的上升序列。
状态计算：
在$(a[i]>a[j])$，$j \in (0,1....i-1)$有 $F[i]=max(F[i], f[j]+1)$

时间复杂度 $O(n^2)$

朴素代码：

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

const int N = 1005;

int n, ans;
int a[N], f[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    ans = 1;
    for (int i = 1; i <= n; i ++) {
        f[i] = 1;
        for (int j = 1; j < i; j ++) {
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
        }
        ans = max(ans, f[i]);
    }
    printf("%d", ans);
    return 0;
}

优化分析：

状态表示： 表示长度$i$的最长上升子序列，末尾最小的数字。
状态计算：
如果$a[i]>F[len]$ 则$F[++len]=a[i]$ 使得最长上升序列长度+1，当前末尾最小元素为$a[i]$
如果$a[i]<=F[len]$ 则说明不会更新当前的长度，但当前的变化会使未来的更长的长度更优，找到第一个 大于或等于$a[i]$ 以更新$F[len]$

时间复杂度 $O(nlogn)$

优化代码

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

const int N = 1005;

int n, len;
int a[N], f[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    f[++ len] = a[1];
    for (int i = 2; i <= n; i ++) {
        if (a[i] > f[len]) {
            f[++ len] = a[i];
        } else {
            int l = 1, r = len;
            while(l < r) {
                int mid = l + r >> 1;
                if (f[mid] >= a[i])
                    r = mid;
                else
                    l = mid + 1;
            }
            f[r] = a[i];
        }
    }
    printf("%d", len);
    return 0;
}

Q.E.D.