B3637 最长上升子序列 題解

· · 题解

B3637 最长上升子序列 題解

管理员注：

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

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

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

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

这道题怎么用 dp 长度呢？

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

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

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

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

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

n 1 2 3 4 5 6
a_n 1 2 4 1 3 4
f(n) 1 2 3 1 3 4

代码实现：