反轉距離

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 

在這個過程中，你將有最大的結果結束。此解決方案的證明並不複雜，您可以自己嘗試。