反转距离

Question

首先让我们回忆一下反演的定义。

包含数字的某个序列S的反演是当S [i]> S [j]和我坦率地说它是我们有无序元素时的情况。例如，对于序列：

1 4 3 7 5 6 2 

我们有以下倒置（4,3），（4,2），（3,2），（7,5）等

我们国家的问题，因为如下所示：反转距离最大（以索引表示）两个反转值之间的距离。例如，我们可以执行人脑搜索，给我们对（4,2）< =>（S [1]，S [6]），并且那里的索引距离是6-1 = 5，这对于此是最大可能的案件。

这个问题可以通过查找所有的倒置和保持最大距离来解决琐碎的方式为O（n^2）（或者，如果我们找到更好的选择更新） 我们还可以有更好的表现反转使用合并排序搜索，因此做在O（nlogn）中相同。 O（n）算法的存在是否存在可能性？请记住，我们只是想要最大距离，我们不想找到所有的反转。请详细说明。

Answer 1

是的，O（n）算法是可能的。

我们可以用贪心算法提取严格递增子：

source:       1 4 3 7 5 6 2 
strictly increasing subsequence: 1 4 7 

然后，我们可以提取严格递减序列倒退：

source:       1 4 3 7 5 6 2 
strictly decreasing subsequence: 1   2 

注意这个严格递减序列被发现后，我们就可以解释它作为递增序列（在正常方向）。

对于这些子序列，我们需要存储的源序列索引的每一个元素。

现在“反转距离”可以通过合并这两个子发现（类似于合并在OP排序提及，但只需要一个合并通）：

merge 1 & 1 ... no inversion, advance both indices 
merge 4 & 2 ... inversion found, distance=5, should advance second index, 
       but here is end of subsequence, so we are done, max distance = 5 

Answer 2

也许我的想法是一样的@叶夫根尼。 这里的解释是：

make a strictly increasing array from the beginning we call it array1 
make a strictly decreasing array from the ending which is array2 (But keep the values in increasing order) 

***Keep track of original indexes of the values of both arrays. 

Now start from the beginning of both arrays. 

Do this loop following untill array1 or array2 checking is complete 

    While(array1[index] > arry2[index]) 
    { 
     check the original distance between array1 index and arry2 index. 
     Update result accordingly. 
     increase array2 index. 
    } 
    increase both array index 

Continue with the loop 

在这个过程中，你将有最大的结果结束。此解决方案的证明并不复杂，您可以自己尝试。