最长递增子序列(LIS)
从一个列表中从左到右挑选数字,每个都比前一个大。这样的链最长能有多长?这个问题简单到可以放进趣味谜题书,而它的答案却把一种纸牌游戏、一个经典的动态规划表格,以及关于随机打乱的最美妙的结果之一联系在一起。
问题
给定一列数字,子序列按原有顺序保留其中一部分。如果每个值都比前一个大,子序列就是递增的。最长递增子序列(LIS)就是最长的这种挑选。一个有 n 个值的列表有 2ⁿ 个子序列,所以逐一检查只适用于非常短的列表。
表格
设 len[i] 为恰好以位置 i 结尾的最长递增子序列的长度。它取以下各项中最大的一个:只有这个值本身时为 1,或者对值更小的更早位置 j 取 1 + len[j]。每个位置都要回看所有更早的位置,所以表格需要 n·(n − 1)/2 次比较。答案是最大的 len[i];记下每个 len[i] 来自哪个 j,就能倒推读出子序列。
一个例子
取 3, 10, 2, 1, 20, 4, 6, 7, 5, 9。逐个位置看,长度依次为 1, 2, 1, 1, 3, 2, 3, 4, 3 和 5:20 延长了 3, 10;4 延长了 3;6 延长了 4,7 延长了 6,9 延长了 7。从 9 倒推得到 3, 4, 6, 7, 9,这是一个长度为 5 的递增子序列。
更快的方法:耐心排序
像发牌一样把值一张张放到牌堆上:每个值放在堆顶不小于它的最左边的牌堆上;如果没有这样的牌堆,就在右边新开一堆。牌堆的数量就是 LIS 的长度。因为各堆的堆顶总是有序的,可以用二分查找找到正确的牌堆,所以整个方法只需 O(n log n) 步。它因与单人纸牌游戏(接龙)相似而得名。
一些数学
1935 年,Paul Erdős 和 George Szekeres 证明:任何由 n² + 1 个不同的数组成的列表,都有一个长度为 n + 1 的递增或递减子序列。1961 年,Stanislaw Ulam 提出问题:把 n 个数随机打乱后,LIS 有多长?答案在 n 很大时接近 2√n,于 1977 年分别由 Anatoly Vershik 和 Sergei Kerov 以及 Ben Logan 和 Larry Shepp 确定。1999 年,Jinho Baik、Percy Deift 和 Kurt Johansson 找到了其涨落的确切形状:来自随机矩阵理论的 Tracy–Widom 分布。
动手探索
打开应用并按“单步”。橙色列是正在计算的位置,蓝色列是与它比较的更早位置。随着找到更长的序列,“长度”行不断增长,“前驱”行记住它们从哪里来;最后答案以橙色倒推读出,并显示在表格下方。
常见问题
LIS 的时间复杂度是多少?
用表格是 O(n²),因为每个位置都要查看每个更早的位置;用耐心排序加二分查找是 O(n log n)。两者都需要 O(n) 的内存。
如何求最长非递减子序列?
允许一个值接在与它相等的值后面:比较时用 ≤ 代替 <。在应用中,勾选“允许相等的值”。用耐心排序时,把每个值放在堆顶严格大于它的最左边的牌堆上。
什么是最长递减子序列?
就是把比较方向反过来的同一个问题,或者是把每个值取相反数后的列表的 LIS。根据 Erdős–Szekeres 定理,足够长的列表总有一个较长的递增子序列或较长的递减子序列。
随机列表的 LIS 有多长?
对于 n 个不同数字的随机打乱,n 很大时接近 2√n。修正项按 n 的六次方根增长,所以对一千个数,平均值约为 58,略低于 2√1000 ≈ 63。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试最长递增子序列