宣传一下 算法基础课整理
题目描述
给定一个长度为 $N$ 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 $N$。
第二行包含 $N$ 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
$1 \le N \le 1000$,
$-10^9 \le 数列中的数 \le 10^9$
输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
算法1
(动态规划) $O(n^2)$
闫氏DP分析法
$$ \begin{cases} \large 状态表示f_i \begin{cases} \large 属性:以i结尾的所有上升子数列\\\ \large 集合:以i结尾的最长上升子数列长度Max \end{cases} \\\ \large 状态转移f_i = \max \{1, \max \limits _ {1 \le j \le i, a_j < a_i}\{ f_j + 1 \} \} \\\ \end{cases} $$
$$\large 答案: \max \limits _ {1 \le i \le n} {f_i}$$
C++ 代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005;
int n, a[N], f[N], res;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", 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[j] + 1, f[i]);
res = max(res, f[i]);
}
printf("%d\n", res);
return 0;
}
我擦你们没开学?对hh
2.8开学
## 既然如此看看我动态吧(
所以你是怎么回事