这个问题起源于讨论的this回答。

This question arose from the discussion in the comments of this answer.

首先，让我们说这是相当困难的界定什么外的顺序。以这个例子帕维尔Shved了，在列表[1,5,10,2,3,4,5,6,7,8,9,10,11]我们可以清楚地看到，5和10（指数1 2）乱序。但是，一个天真的算法，只是简单地检查某种排序列表不变会不会点那些出来。

First, let's say it's quite difficult to define what out-of-order is. Taking the example Pavel Shved gave, in the list [1,5,10,2,3,4,5,6,7,8,9,10,11] we can "clearly" see that 5 and 10 (indices 1 and 2) are out of order. But a naïve algorithm that simply checks some kind of sorted list invariant would not point those out.

检查 A [I-1] = A [1]所有0℃; I＆LT; = N 将产生的元素索引3（这2）;

checking a[i-1]<=a[i] for all 0<i<=N would yield the element at index 3 (which is 2);

检查 A [J] LT = A [1]所有0℃= I＆LT; = N和0℃= J＆LT; = I 将产生在指数的3至12的所有元素;

checking a[j]<=a[i] for all 0<=i<=N and 0<=j<=i would yield all elements in indices 3 to 12;

我的问题是：你能想到一个算法来解决这个问题得到了正确答案（即指数1和2）？如果是这样，在什么时间和内存的复杂性会运行它？

My question is: can you think of an algorithm to solve this problem that yields the "correct answer" (i.e. indices 1 and 2)? If so, under what time and memory complexity would it run?

推荐答案

可能是对此最好的办法是先找到的最长递增子再考虑该序列的不属于被淘汰的顺序排列的所有元素。所提供的链接页面上的算法运行为O（n log n）的时间和使用 O（N）空间（此外，该列表本身）。

Probably the best approach to this would be to first find the longest increasing subsequence and then consider all elements not part of that sequence to be out of order. The algorithm provided on the linked page runs in O(n log n) time and uses O(n) space (in addition to that of the list itself).

这样一种方法肯定会产生正确的答案为您的示例情况下，由于最长递增子将是1至11的序列不包括额外的5和10。

Such an approach would definitely yield the correct answer for your example case, since the longest increasing subsequence would be the 1 through 11 sequence not including the extra 5 and 10.