<—点个赞吧QwQ

宣传一下算法基础课整理

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

输入格式

第一行包含整数 $ N $ 。

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

输出格式

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

数据范围

$ 1 \le N \le 1000 $ ，
$ -10^9 \le 数列中的数 \le 10^9 $

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

思路

闫氏 $ \text{DP} $ 分析法：
状态表示： $ f_i $

• $ f_i $ 表示从第一个数开始算，以第 $ i $ 个数结尾的最长上升子序列

状态计算：

• 如果我们选第 $ 1 $ 个数，且第 $1$ 个数小于第 $i$ 个数，那么对应的就是 $ f_1 $
• 如果我们选第 $ 2 $ 个数，且第 $2$ 个数小于第 $i$ 个数，那么对应的就是 $ f_2 $
• 如果我们选第 $ j $ 个数，且第 $j$ 个数小于第 $i$ 个数，那么对应的就是 $ f_j $
• 所以状态转移方程就是 $ f_i=\underset{1\le j<i\& a_j< a_i}\max\lbrace f_j+1\rbrace $

初始化：

• 因为每一个数以自己结尾的最长上升子序列的长度为 $ 1 $ ，所以初始 $ \underset{1\le i \le n}{f_i}=1 $

答案：

• 根据定义，由于每一个数都有可能成为最长上升子序列的最后一个数，所以答案就是 $ \underset{1\le i\le n}\max \lbrace f_i \rbrace $

代码

#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int ans = 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);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << endl;
    return 0;
}