<—点个赞吧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;
}