JavaScriptでペアの最小値合計を最大化するアルゴリズムを解説

この記事では、整数の配列を受け取り、ペアごとの最小値の合計が最大になるようにグループ分けするJavaScript関数の実装方法を解説します。

問題の概要

長さ2nの整数配列 arr を引数として受け取るJavaScript関数を作成します。この関数の目的は、配列内の整数をn個のペア (a1, b1), (a2, b2), ..., (an, bn) にグループ化し、各ペアの最小値 min(ai, bi) の合計（i = 1 から n まで）ができるだけ大きくなるようにすることです。

例えば、次の入力が与えられたとします。

const arr = [1, 4, 3, 2];

この場合、期待される出力は次の通りです。

const output = 4;

出力の解説

この例では n = 2 であり、ペアを (1, 2) と (3, 4) に分けると、min(1, 2) + min(3, 4) = 1 + 3 = 4 となり、これが最大の合計になります。

解法のポイント

この問題を効率的に解く鍵は、配列を昇順にソートすることです。小さい数同士、大きい数同士をペアにすると、各ペアの最小値ができるだけ大きくなります。逆に、大きい数と小さい数をペアにしてしまうと、小さい方が必ず最小値として選ばれ、大きい数が損をしてしまいます。

コード例

以下が実際のコードです。

const arr = [1, 4, 3, 2];
const pairSum = (arr = []) => {
    arr.sort((a, b) => a - b)
    let sum = 0
    for (let i = 0; i < arr.length; i += 2) {
        sum += Math.min(arr[i], arr[i + 1])
    }
    return sum
}
console.log(pairSum(arr));

コードの流れ

処理の手順は以下の通りです。

まず、sort() メソッドを使って配列を昇順に並べ替えます。比較関数 (a, b) => a - b を渡すことで、数値として正しくソートされます。次に、forループを2ステップずつ進めながら、隣り合う2つの要素（arr[i] と arr[i + 1]）のうち小さい方を Math.min() で取り出し、合計に加算していきます。ソート済みの配列では arr[i] が常に arr[i + 1] 以下になるため、実質的には偶数インデックスの要素を足し合わせていることになります。

出力結果

コンソールには次の出力が表示されます。

4

計算量について

この解法の時間計算量は、ソート処理が支配的となるため O(n log n) です。空間計算量は、JavaScriptのsort()が内部で行う処理に依存しますが、追加のデータ構造を必要としないため O(1)〜O(log n) 程度で抑えられます。シンプルで効率的なアプローチと言えるでしょう。