已填格子
比较次数
目前最长

  • 正在填写
  • 被读取
  • 答案

更多关于最长递增子序列

最长递增子序列(LIS)

在一列数字中,保持原有顺序,最多能挑出多少个数,使每个数都比前一个大?最长递增子序列回答的就是这个问题。输入一列数字,观看动态规划如何为每个位置求出以它结尾的最长序列。 按“播放”观看表格逐步填满,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。输入一列数字。对每个位置,表格记录以该位置结尾的最长递增数值序列的长度,以及它所接续的前一个位置。勾选“允许相等的值”可求从不下降的序列。最后从序列的最后一个值开始倒推读出整个序列。“新示例”会生成另一列数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 输入一列数字,用逗号或空格分隔。勾选“允许相等的值”可求从不下降的序列。
  2. 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到任意位置。
  3. 观察每个位置与所有更早的位置逐一比较,然后看最长序列以橙色倒推读出。

表格如何运作

表格有三行:值、以每个位置结尾的最长递增子序列的长度,以及它所接续的位置。单独一个值就是长度为 1 的序列。然后检查每个更早的位置:如果那里的值更小,以那里结尾的序列就可以用当前值延长,长度比它多 1。最长的延长胜出,它的位置写入第三行。

倒推读出序列

最长递增子序列结束于长度最大的位置。从那里开始,第三行说明它前面是哪个位置,而那个位置的第三行又说明再前面是哪个位置,直到遇到前面没有位置的那一个。按顺序读出这些值,就是答案。勾选“允许相等的值”后,一个值也可以接在与它相等的值后面,这样得到的是从不下降的最长序列。

常见问题

子序列和子数组有什么区别?

子数组是一段相邻的值。子序列保持顺序,但可以跳过一些值,所以在 3, 10, 2, 1, 20 中,3, 10 和 20 构成一个递增子序列,尽管 2 和 1 位于它们之间。

LIS 算法有多快?

表格方法比较每一对位置:n 个值需要 n·(n − 1)/2 次比较。耐心排序只需 O(n log n):它为每种长度保存能结束该长度序列的最小值,并用二分查找放置每个新值。

最长递增子序列唯一吗?

不一定。在 1, 3, 2, 4 中,1, 3, 4 和 1, 2, 4 的长度都是 3。表格给出长度,倒推找出其中一个。

最长递增子序列用在哪里?

用于比较文件和基因组:有些方法先找出匹配的行,再取它们位置的递增子序列;用于排程和箱子堆叠类谜题;还用于数学:随机打乱的列表的 LIS 长度是一个著名的研究对象。

会向任何地方发送数据吗?

不会。所有计算都在你的浏览器中完成,你最近的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器