arrays - 如何检查每个元素是否在数组的任何最长递增子序列中？

我们有一个整数数组。对于每个元素，我们想知道该元素是否至少包含在一个 LIS 中。我们阵列的许多 LIS 的。我们想在小于 O(n²) 的时间内知道数组中所有元素的这一点。

例如数组 [2, 4, 3, 2, 5] 有两个 LIS。数组中的所有元素至少属于这些 LIS 之一，但不属于任何 LIS 的 4^th 元素除外。

我知道一个使用 dfs 的简单解决方案，但它的运行时间是 O(n²)。

最佳答案

运行算法，例如 https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms它在每个点计算在该点结束的最长递增子序列的长度。

使用相反顺序的数据运行相同的算法，为每个点计算从该点开始的最长递增子序列的长度。

对于每个点添加两个计算长度。如果这个和等于找到的最大和，则该点位于最长递增子序列上。

所引用的算法每次通过都需要时间 O(n log n)，而总和仅为 O(log n)，因此总数为 O(n log n)

关于arrays - 如何检查每个元素是否在数组的任何最长递增子序列中？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45067878/