1

这是最长递增子序列问题的变体。假设您不想找到一个序列或计算有多少个序列，而是想识别可能是某个最长递增序列的一部分的项目。

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

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

4

1 回答 1

1

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

在示例的情况下1,2,4,3,0,5，它会像这样工作：

  • 1位于索引 0 处，因此在没有先前索引的情况下给它 1 的 lis 分数
  • 2前面可以有1，所以2得到 1+1=2 的 lis 分数和 0 的前一个索引
  • 4可以在2and之前1，但2具有更好4的 lis 得分，因此获得 2+1=3 的 lis 得分和之前的索引 1
  • 3也可以在 and 之前2，1并且再次2具有更好3的 lis 分数，因此获得 2+1=3 的 lis 分数和之前的索引 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,...具有二次边数，因此您需要避免将它们全部存储或全部探索。

于 2014-05-20T14:06:48.253 回答