配對陣列的最小最大和

Question

我有一個長度均勻的整數數組。作爲一個例子，讓我們來看一個數組{0, 6, 4, 22, 19, 11}。將所有數字配對成對，我必須找到最大的一對數。現在，在所有可能的組合中，我必須找到最大的配對總和最小的情況。 在這種情況下，它將是23（當對是0-22,4-19,6-11）。

現在我能想到的是檢查每一個可能的集對資金的，發現最大的一對，並檢查它是否比上一次小的唯一案例。然而，這個效率非常低，因爲它需要在陣列中循環長度的平方時間。我想知道是否有更有效的方法來做到這一點。

我考慮到排數組，並找到最大的一筆來自第一和最後一個元素選擇對，然後向內移動，可以工作，但我不知道這是在所有情況下都是這樣。

Answer 1

是的，對所有情況都是如此！可以數學證明！

假設2N數字A_1，A_2，A_3，A_4，...，a_2N是非人數減少（後排序）。然後，對爲

A_1和a_2N

A_2和a_2N-1

...

A_N和A_N + 1

最大，這些款項將是最小的。

假設A_I和a_2N + 1-i的一對獲得最大值MAX。

那麼我們將改變對來看看我們是否能夠得到較小的最大值。因此，a_2N + 1-i只能與a_1，a_2，...，a_i-1配對以獲得較小的最大值，同樣，a_2N + 2-i也只能與a_1，a_2，...，a_i配對-1，...，所以對於a_2N。

總的來說，我們有i個數字（a_2N + 1-i，...，a_2N）必須與i-1數字（a_1，a_2，...，a_i-1）配對，這是不可能的。

所以我們可以得出結論證明。

我不知道我是否有這個說法顯然。

祝你好運！