algorithm - 如何选择列表中乱序的所有元素？

Question

这个问题来自this answer的评论中的讨论。 .

首先，假设定义什么是无序是相当困难的。以 Pavel Shved 给出的例子为例，在列表 [1,5,10,2,3,4,5,6,7,8,9,10,11] 中我们可以“清楚地”看到 5 和 10(索引 1和 2) 出现故障。但是简单地检查某种排序列表不变量的朴素算法不会指出这些。

• 检查 a[i-1]<=a[i] for all 0<i<=N将产生索引 3(即 2)处的元素；

• 检查 a[j]<=a[i] for all 0<=i<=N and 0<=j<=i将产生索引 3 到 12 中的所有元素；

我的问题是:你能想出一种算法来解决这个问题并产生“正确答案”(即索引 1 和 2)吗？如果是这样，它会在什么时间和内存复杂度下运行？

Answer 1

最好的方法可能是首先找到 longest increasing subsequence然后将不属于该序列的所有元素视为无序。链接页面上提供的算法在 O(n log n) 时间内运行并使用 O(n) 空间(除了列表本身的空间)。

这种方法肯定会为您的示例案例产生正确的答案，因为最长的递增子序列是 1 到 11 序列，不包括额外的 5 和 10。