如何在O(n)或O(nlogn)中找到包含重复项的最长不减子序列？

Question

我们知道了一种在O(nlogn)中找到最长增长子序列的算法。我想知道我们是否能找到时间复杂度相近的最长的不递减子序列？例如，考虑一个数组：(4,10,4,8,9)。最长的增长子序列为(4,8,9)。最长的不减子序列为(4,4,8,9)。

Answer 1

我认为以下内容将适用于O(nlogn)

从右到左扫描数组，并为每个元素解决从数组的给定元素开始寻找最长子序列的子问题。例如，如果数组的索引从0到4，那么从子数组4,4开始，检查从4开始的最长序列，然后检查子数组3,4和从3开始的最长的子序列，接下来的2,4等等，直到0,4。最后，选择在这两个步骤中建立的最长的子序列。

对于最后一个元素(so子数组4,4)，最长的序列总是长度为1。

在下一次迭代中，您考虑左边的另一个元素(例如，在第二步中，考虑子数组3、4，因此新元素是原始数组中的索引3的元素)，检查该元素是否大于其右侧的一些元素。如果是这样的话，您可以从右边获取某个元素的结果并添加一个。

例如：

• 4,4 ->最长序列1 (9)
• 3,4 ->最长序列2 (8,9) 1+1 (从上面取最长序列，从9开始并加上1)
• 2，4 ->最长序列3 (4,8,9) 2+1 (从上面取最长序列，即(8,9)，
• 1，4 ->最长的1 (10)序列(10大于其右边的所有元素)
• 0，4 ->最长的4 (4,4,8,9) 3+1 (你取上面最长的序列，即(4,8,9)，再加上1到它的长度)

主要问题是如何在对数时间内浏览所有候选人的右边。为此，您保留了一个排序映射(一个平衡的二叉树)。键是已经访问过的数组元素。这些值是从该元素获得的最长序列长度。不需要存储重复项-在重复键中存储具有最大值的条目。

Answer 2

首先，这里有一个“黑匣子”方法，它将允许您使用现成的最长增长子序列的求解器来找到最长的不递减子序列。让我们拿出您的样本数组：

4, 10, 4, 8, 9

现在，假设我们通过向每个数字添加一个很小的分数来转换这个数组，如下所示：

4.0, 10.1, 4.2, 8.3, 9.4

用这种方式更改数字不会改变两个不同整数之间比较的结果，因为整数分量的大小差异比小数点之后的值更大。但是，如果现在比较两个4，则后4个比较比前一个要大。如果您现在找到最长的不递减子序列，您将得到[4.0, 4.2, 8.3, 9.4]，然后您可以映射回[4, 4, 8, 9]。

更普遍的情况是，如果您使用的是n个整数值的数组，则可以将I/n添加到每个数字中，其中I是其索引，您将得到一系列不同的数字。从这里开始，运行一个常规的LIS算法就可以做到这一点。

如果你不能用这种方法处理分数，你也可以把每个数乘以n，然后再加上i，这也是有效的。

另一方面，假设您有LIS求解器的代码，并希望将其转换为解决最长的不递减子序列问题的代码。上面的推理表明，如果您将以后的数字副本视为比以前的副本“更大”，那么您可以只使用常规的LIS。在此情况下，只需阅读LIS的代码，并找到进行比较的地方。当对两个相等的值进行比较时，考虑到后面的外观比前一个更大，从而打破了平局。