algorithm - 找到所有最长递增子序列的最优化算法是什么？

Question

我试图找到一个数组的所有最长递增子序列。我可以按照建议使用二进制搜索在 O(n log n) 中找到一个这样的 LIS on Wikipedia .

有人可以帮助我吗，我如何扩展相同的功能以找到所有此类 LIS。我找不到比 O(n²) 更好的方法了。任何优化建议都会非常有帮助。

Answer 1

考虑这个列表:

2,1, 4,3, 6,5, 8,7, 10,9, ..., 2m,2m-1

这个列表的最长递增序列长度是m = n/2。您可以通过从每“对”项目中选择一个元素来轻松构建这样的序列。因为有 m 个这样的对，并且选择是独立的，所以有 2^m 个最长的递增序列。

所以你的算法不能比 Ω(2^(n/2)) 快，因为在某些情况下至少有那么多输出。

要解决这个问题，您需要调整问题，也许可以通过执行 output-sensitive analysis 来解决。或者通过计算序列的数量而不是实际生成它们。另一种选择是输出一种紧凑的方式，以后可以使用它来生成所有序列，这就是线性时间unification。算法可以。