自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:05，当前版本为作者最后更新于2022-07-01 14:32:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3637 最长上升子序列 題解

管理员注：

阅读本文章前，请先阅读$\ \texttt{ShanCreeper}$ B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】

点赞上文章即代表您已阅读并熟知其内容。

给定一个正整数序列，输出这个序列中最长上升子序列的长度。

这道题怎么用 dp 长度呢？

如果一个上升子序列的最大值小于一个在它后面的数，那么这个数和这个子序列可以拼成一个更长的上升子序列。

例如一组数据：1,2,4,1,3,4。

我们知道，1,2,3 为一个上升子序列，但是 3 后面的 4 和这个上升子序列拼接后可以组成一个更长的上升子序列。

所以，我们可以设计 $f(i)$，表示以第 $i$ 个数为结尾的最长上升子序列的长度。

再以上面的数据为例子，就可以列出表格：

代码实现：

• 读入数据；

• 大循环开始，从 $1$ 到 $n$，计算 $f_i$，记得初始值是 $1$；

• 小循环，从 $1$ 到 $i-1$，如果 $a_j$ 小于 $a_i$ 的话，说明这个数可以和 $f_i$ 组成上升子序列，则 $f_i$ 取 $\max (f_i,f_j+1)$；

• 寻找最大值；