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

Question

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

有人可以帮助我，我如何扩展它来查找所有此类 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))，因为在某些情况下至少有那么多输出。

为了解决这个问题，您需要调整问题，可能通过进行输出敏感分析或通过计算序列的数量而不是实际生成它们。另一种选择是输出一种紧凑的方式，以后可以使用它来生成所有序列，这就是线性时间统一算法所做的。

Answer 2

这样的序列可以成倍增加。您当然不能在二次时间中枚举它们。

您可以在 O(n log(n)) 时间内找到从数组中每个位置开始和结束的最长递增子序列的长度。然后，您可以通过简单的递归枚举所有最长的递增子序列。