algorithm - 确定数组中的哪些项目是最长递增子序列的一部分

Question

这是 longest increasing subsequence problem 的变体.假设，而不是想找到一个序列或 counting how many sequences there are ，您想要识别可以属于一些最长递增序列的项目。

例如，在列表 1,2,4,3,0,5 中，除零之外的所有项目都可以是最长递增子序列的一部分。

找到这些项目的策略是什么？完成效率如何？

Answer 1

一种方法是使用与最长递增子序列问题相同的动态算法，跟踪第 i 项之前的最佳项，假设它是最后一项，但对其进行调整跟踪关系。然后，在知道每个项目的最佳前面项目后，确定从得分最高的项目开始时可以通过该图表到达哪些项目。

在示例中，1,2,4,3,0,5，它会像这样工作:

• 1 在索引 0 处，所以给它一个 lis 分数 1，没有之前的索引
• 2 可以在 1 之前，因此 2 得到的 lis 分数为 1+1=2 并且前一个索引为 0
• 4 可以在 2 和 1 之前，但是 2 有更好的 lis 分数所以 4 得到 lis 分数 2+1=3 和前一个索引 1
• 3 也可以在 2 和 1 之前，同样 2 有更好的 lis 分数所以3 得到 lis 分数 2+1=3 和前一个索引 1
• 0 前面不能有任何内容，所以它的 lis 分数为 1，没有之前的索引
• 5 可以在任何其他项目之前，但是 3 和 4 具有最好的 lis 分数 (=3) 所以 5 的 lis 分数为 3+1=4，之前的索引为 2 或 3。

现在我们采用得分最高的项目，在本例中为 5，然后迭代地向后搜索可能位于它之前的项目。这将标记 5、3、4、2 和 1(但不是0) 作为最长序列。

这肯定会在 O(n^2) 时间内运行，而且我认为如果聪明的话，它可以在 O(n lg n) 时间内运行。

从二次时间出发的主要挑战不是制作一个具有“可以最佳先于”边的显式图。像 1,1,1,1,1,1,...,2,2,2,2,2,2,... 这样的列表有平方数的边，所以你需要避免将它们全部存储或全部探索。