我们知道有一种算法可以在 O(nlogn) 中找到最长递增子序列。我想知道我们是否能找到时间复杂度相似的最长非递减子序列？
例如，考虑一个数组：(4,10,4,8,9)。
最长的递增子序列是(4,8,9)。
最长的非递减子序列是 (4,4,8,9)。
首先，这是一种“黑匣子”方法，可让您使用现成的最长递增子序列求解器找到最长的非递减子序列。让我们看一下您的示例数组：
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 的代码并找到进行比较的地方即可。当对两个相等的值进行比较时，通过认为后一个值大于前一个值来打破平局。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
