$\LARGE\color{orange}{刷题日记(算法提高课)}$

我们定义 $f[i]$ 所表示的集合为：以 $a[i]$ 为结尾的所有严格上升的子序列，$f[i]$ 的属性为：所有子序列当中长度的最大值

我们当前需要对 $f[i]$ 所表示的集合进行划分，并且 $f[i]$ 为结尾元素，因此我们考虑倒数第二个元素的可能性

显然，倒数第二个元素可能不存在，也可以是从 $a[1]$ 到 $a[i-1]$ 当中满足 $a[k]<a[i]$ 的任意一个元素

也就是说，$f[i]$ 最小都会为 1 ，我们的讨论也是在此基础上进行的

不难得出状态转移方程为：$f[i]\ =\ max(f[i],\ f[k]\ +\ 1)$

最后对 $f[i]$ 当中的所有数取一个最大值即可

代码如下：

#include <iostream>

using namespace std;

const int N = 1010;
int f[N], a[N];
int 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;
        for(int j = 1; j < i; j++)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}