方法一：简单dp($O(n^2)$)

• f[i] 表示以a[i]结尾的子序列的最大长度
• f[i] = max(f[j] + 1), j < i && a[j] < a[i]

#include <iostream>
using namespace std;

const int N = 1010;
int a[N], f[N];

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

    int res = 0;
    for(int i = 1; i <= n; i ++ ){
        f[i] = 1;
        for(int j = 1; j < i; j ++ )
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}

方法二：dp+二分($O(nlogn)$)

• f[i] 表示以长度为i的最长上升子序列末尾最小的数字
• 状态计算：对于每一个a[i], 如果大于f[cnt-1](下标从0开始，cnt长度的最长上升子序列，末尾最小的数字)，那就cnt+1，使得最长上升序列长度+1，当前末尾最小元素为a[i]。 若a[i]小于等于f[cnt-1],说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个大于或等于 (这里不能是大于) a[i]，更新以那时候末尾的最小元素。

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], f[N];

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

    int cnt = 0;
    f[cnt ++ ] = a[0];
    for(int i = 1; i < n; i ++ ){
        if(a[i] > f[cnt - 1]) f[cnt ++ ] = a[i];
        else{  // 找出找到第一个大于或等于a[i]，更新以那时候末尾的最小元素
            int l = 0, r = cnt - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(f[mid] >= a[i]) r = mid;
                else l = mid + 1;
            }
            f[l] = a[i];
        }
    }
    cout << cnt << endl;
    return 0;
}