JavaScriptで整数リスト内の2つの数値の最大積を求める方法

問題の概要

整数の配列を唯一の引数として受け取るJavaScript関数を作成する必要があります。

この関数の目的は、配列内の任意の2つの要素を掛け合わせたときに得られる最大の積を見つけることです。ただし、線形時間（O(n)）かつ定数空間（O(1)）で処理を完了しなければならないという条件が課されています。

例

入力配列が次の場合を考えてみましょう。

const arr = [3, 9, 2, 1, 0];

このとき、出力は次のようになります。

const output = 27;

これは、3と9を掛け合わせた27が最大の積となるためです。

アプローチの解説

最大の積が生まれるのは、次の2つのケースのいずれかです。

• 配列内の最大値と2番目に大きい値の積（正の数同士を掛ける場合）
• 配列内の最小値と2番目に小さい値の積（負の数同士を掛けると正の数になる場合）

そこで、配列を一度だけ走査しながら、大きい方から2つの値（変数 a、b）と小さい方から2つの値（変数 c、d）を同時に追跡します。走査が終わった時点で、両者の積を比較し、大きい方を返せば答えが得られます。この方法なら、ソートを行わずに時間計算量O(n)、空間計算量O(1)という条件を満たすことができます。

コード例

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

const arr = [3, 9, 2, 1, 0];
const maxPairProduct = (arr = []) => {
   let c = Infinity, d = c;
   let a = -Infinity - 1, b = a;
   for (const n of arr) {
      if(n >= a){
         b = a;
         a = n;
      }else if(n >= b){
         b = n;
      };
      if(n <= d){
         c = d;
         d = n;
      }else if(n <= c){
         c = n;
      };
   };
   return Math.max(a * b, c * d);
};
console.log(maxPairProduct(arr));

出力結果

コンソールには次のように出力されます。

27

まとめ

このアルゴリズムのポイントは、配列をソートせずに1回のループで必要な4つの値（上位2つと下位2つ）を追跡できる点です。負の数を含む配列でも正しく動作し、大規模なデータセットに対しても効率的に処理できる実用的な手法です。