ペア配列の最小の最大和

Question

私は、偶数の長さを持つ整数の配列を持っています。たとえば、配列{0, 6, 4, 22, 19, 11}を取るとします。すべての数をペアにすると、私は最大のペアの合計を見つけなければなりません。さて、すべての可能な組み合わせの中で、私はペアの和のうち最大のものが最小である場合を見つけなければなりません。 この場合は23になります（ペアが0-22、4-19、6-11の場合）。

私が考えることができる唯一のケースは、可能なすべてのペアの合計を調べ、最大のペアを見つけて、それが最後の時間よりも小さいかどうかをチェックすることです。しかし、これは、配列の長さの2乗に反してループを繰り返す必要があるため、非常に非効率的です。もっと効率的なやり方があるのだろうかと思っています。

私は配列をソートし、最初と最後の要素からペアを選択して内方に移動すると最大の合計を見つけることができますが、すべての場合に該当するかどうかはわかりません。

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。

私たちの数字（a_2N + 1-i、...、a_2N）はi-1の数字（a_1、a_2、...、a_i-1）と対になっていなければなりません。

私たちは結論を証明することができます。

私はこれを明確に述べているかどうかはわかりません。

Best Luck！