AcWing 895. 最长上升子序列

题目

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式 第一行包含整数 $N$。

第二行包含 $N$ 个整数，表示完整序列。

输出格式 输出一个整数，表示最大长度。

数据范围 $1≤N≤1000，−10^9≤数列中的数≤10^9$ 输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

思路

状态表示 -- 集合：从前i个物品选，形成递增子序列的长度的集合
         -- 属性：长度
状态计算：
    当遍历到第i个物品时，子序列可能是1~i-1中的传递过来
    从1跳到i: f[i] = f[1] + 1
    从2跳到i: f[i] = f[2] + 1
    ...
    从i-1跳到i: f[i] = f[i - 1] + 1
由以上可知核心公式为：f[i] = max(f[1] + 1, f[2] + 1, ..., f[i - 1] + 1)

代码

#include <iostream>

using namespace std;

const int N = 1010;


int a[N];
int f[N];

int main()
{
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;  // 对于每个数值，默认子序列长度为1
        for (int j = 1; j < i; j ++ )
        {
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
        }
    }
    
    int res = 0;  // 最终结果不一定是f[n]，要取max
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    
    cout << res << endl;
    
    return 0;
}