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

Question

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

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

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

Answer 1

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

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

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

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