DP暴力枚举，时间复杂度O($n^2$)

转移方程

 当 j == 0,                    f[i] = 1;//什么都没有只有自己
 当 0 < j < i 且 a[j] < a[i] , f[i] = max(f[1], f[2], ..., f[j]) + 1;
 //暴力枚举一下前面所有满足条件状态的f[j]

#include <iostream>

using namespace std;

const int N = 1010;

int f[N];
int a[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 = 0; j < i; j ++ ) // 枚举0 ~ i - 1的所有状态
            if (a[j] < a[i] || j == 0) // j == 0 这个状态也可以直接写到前面
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;

    return 0;

}

求方案数

#include <iostream>

using namespace std;

const int N = 1010;

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

    for (int i = 1; i <= n ; i ++ )
    {
        f[i] = 1;//最长公共自序列至少是它本身
        g[i] = 0;
        for (int j = 1; j < i; j ++ )
            if(a[j] < a[i])
            {
                if(f[i] < f[j] + 1)
                {
                    g[i] = j;
                    f[i] = max(f[i], f[j] + 1); 
                }

            }

    }

    int k = 1, res = 0;
    for (int i = 1; i <= n; i ++ ) 
        if(f[k] < f[i]) k = i, res = f[k];

    for (int i = 0, len = f[k]; i < len; i ++) 
    {
        cout << a[k] << endl;
        k = g[k];
     }

    cout << res << endl;

    return 0;
}

利用二分查找维护一个下标作为长度，最小值数组， 时间复杂度O(nlogn)

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int a[N];
int q[N];//q[i]存储的是枚举到当前阶段长度是i末尾最小的数
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    int len = 0;
    for (int i = 1; i <= n; i ++ )//枚举到第i个数
    {
        int l = 0, r = len;//二分q数组
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        //如果最小值是最后一个数字，则需要在后面加上这个数字，len更新
        len = max(len, l + 1);
        //更新l + 1长度的最小值
        q[l + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}