JavaScriptで配列からn個の数値を選び、最大の積を返す方法

JavaScriptでは、第一引数として数値の配列、第二引数として数値 n を受け取る関数を作成することが求められます。

この関数は、配列の中から n 個の数値を選んだときに実現できる最大の積を計算し、その結果を返します。

アプローチのポイント

最大の積を求めるには、単純に大きい数字だけを選べばよいわけではありません。負の数同士を掛けると正になるため、絶対値が大きい負の数2つの積が、小さい正の数2つの積を上回るケースがあります。

そこで、以下のような戦略を取ります。

• まず配列を昇順にソートします。
• n が配列の長さより大きい場合、また n が奇数かつ配列の最大値が負の場合は、有効な結果が得られないため undefined を返します。
• n が奇数の場合は、最大の数（多くの場合、最大の正の数）を1つ先に取り出して prod に掛け、残りの個数を偶数にします。
• 残りの選択では、「最も小さい2つの数の積」と「最も大きい2つの数の積」を比較し、大きい方を prod に掛けていきます。これにより、負の数同士の組み合わせも適切に考慮されます。

コード例

実際のコードは次のようになります。

const getHighestProduct = (arr, num) => {
   let prod = 1;
   const sorter = (a, b) => a - b;
   arr.sort(sorter);
   if (num > arr.length || num % 2 && arr[arr.length - 1] < 0) {
      return;
   };
   if (num % 2) {
      prod = arr.pop();
      num--;
   };
   while (num) {
      prod *= arr[0] * arr[1] > arr[arr.length - 2] * arr[arr.length - 1]
      ? arr.shift() * arr.shift() : arr.pop() * arr.pop();
      num -= 2;
   };
   return prod;
}
console.log(getHighestProduct([1, 10, -5, 1, -100], 3));
console.log(getHighestProduct([3, 4, 5, 6, 7], 3));
console.log(getHighestProduct([3, 4, -5, -6, -7], 3));

実行結果

コンソールに出力される結果は次のとおりです。

5000
210
168

処理の流れを確認

1つ目の例 [1, 10, -5, 1, -100] で n = 3 の場合を見てみましょう。

1. ソート後の配列は [-100, -5, 1, 1, 10] となります。
2. n が奇数なので、最大値 10 を取り出し、prod = 10、残り n = 2 となります。
3. 残りの比較では、最小2つの積 (-100) × (-5) = 500 が最大2つの積 1 × 1 = 1 より大きいため、500 を採用します。
4. 結果として 10 × 500 = 5000 が返されます。

このように、負の数同士の積も考慮することで、常に最大の積を正確に求められるのがこのアルゴリズムの強みです。