從兩個陣列中選擇一對

給定2個陣列A和B，長度分別爲n和m。從兩個陣列中選擇一對

我想找到一個對（A [i]，B [j]）使得和A [i] + B [j]最大，但是在給定的整數k和1的情況下，ji> k < = i < = n，1 < = j < = m。

我知道一個簡單的O（n * m）天真的方法來解決它，但是他們有更好的方法來做到這一點。

讓我舉個例子說我們有兩個數組A = [5,10,9,7,10]和B = [0,0,0,4,1,2，-2]並且說K = 3然後我必須從A和B中選擇一個元素，使得所選元素的位置之間的差異至少爲k。在這種情況下，我們可以看到ans是12.通過選擇A中的第2個元素和B中的第6個元素。

希望它講清楚明白的問題

來源

2013-12-09 user3080139

使用動態編程:)創建陣列MAXB與長度爲m，指數MAXB i的指示從i到陣列B的米的最大值maxB可以通過maxB [i] = max（B [i]，maxB [i + 1]）在O（n）中容易地完成。那麼你只需遍歷A元素max = max（A [i] + maxB [i + k]，max）。複雜度是O（n） –

你可以通過上面的例子更清楚地說明嗎？？Thnx。如何maxB可以在O（n）中完成。它應該是O（m）我猜 – user3080139

在你的例子中，maxB = {4,4,4,4,2,2，-2};因此從A = 1開始到5，我們有max = A [1] + maxB [1 +（K + 1）] = 9，那麼對於i = 2，max = A [2] + maxB [2 + （K + 1）] = 12 ...我們有最大= 12 :) n是常數，所以應該是O（max（n，m）） –

這裏是方式做到這一點在O(N+M)： -

生成最大陣列其中max [i]表示在子陣列b最大元素[I到M]

max[m] = b[m]   
for(i=m-1;i>=1;i--) 
    max[i] = maximum(max[i+1],b[i]);

對所有的有效對計算maxpair如下： -

maxpair = -infinity; 


for(i=1;i<=n;i++) { 

    if(i+k+1<=m) { 

    maxpair = maximum(maxpair,a[i]+max[i+k+1]); 

    } 

}

來源

2013-12-09 04:45:41

從兩個陣列中選擇一對

回答

相關問題