【JavaScript】線形時間O(n)で配列内の2つの整数の最大積を求める方法

本記事では、正の数と負の数が混在する数値配列を受け取り、たった1回の走査（線形時間 O(n)）で「2つの数値の積」の最大値を返すJavaScript関数の実装方法を解説します。

アプローチのポイント

最大積を求めるうえで重要なのは、次の2つのケースを必ず比較することです。

• 配列内の最も大きい2つの数の積（例：8 × 7）
• 配列内の最も小さい（絶対値の大きい負の）2つの数の積（例：-5 × -4 = 20）

負の数同士を掛けると正になるため、「小さい方の2つの数」の積が「大きい方の2つの数」の積を上回るケースがあります。そこで、配列を1回だけ走査しながら「大きい方の上位2つ」と「小さい方の下位2つ」を同時に追跡し、最後に両者の積を比較すれば答えが得られます。

実装コード

const arr = [-1, -3, -4, 2, 0, -5];
const arr2 = [2, 3, 5, 7, -7, 5, 8, -5];

// 配列内の全要素の積を計算するヘルパー関数
const produce = arr => arr.reduce((acc, val) => acc * val);

const maximumProduct = (arr = []) => {
    const [first] = arr;

    // 空配列の場合は 0 を返す
    if (!first) {
        return 0;
    }

    // reduce で1回の走査により「大きい方2つ」「小さい方2つ」を同時に追跡
    const creds = arr.reduce((acc, val) => {
        const { min, max } = acc;

        // 最大値より大きければ順位を一つずらして更新
        if (val > max[0]) {
            max[1] = max[0];
            max[0] = val;
            return acc;
        }

        // 最小値より小さければ順位を一つずらして更新
        if (val < min[0]) {
            min[1] = min[0];
            min[0] = val;
            return acc;
        }

        // 2番目に大きい値を更新
        if (val > max[1]) {
            max[1] = val;
            return acc;
        }

        // 2番目に小さい値を更新
        if (val < min[1]) {
            min[1] = val;
            return acc;
        }

        return acc;
    }, {
        min: [first, first],
        max: [first, first]
    });

    const { max, min } = creds;

    // 「大きい2つの数の積」と「小さい2つの数の積」を比較して大きい方を返す
    return produce(max) > produce(min) ? produce(max) : produce(min);
};

console.log(maximumProduct(arr));
console.log(maximumProduct(arr2));

実行結果

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

20
56

結果の検証

最初の配列 [-1, -3, -4, 2, 0, -5] の場合：

• 大きい方の2つの数：2 × 0 = 0
• 小さい方の2つの数：-5 × -4 = 20 ← 最大積

2番目の配列 [2, 3, 5, 7, -7, 5, 8, -5] の場合：

• 大きい方の2つの数：8 × 7 = 56 ← 最大積
• 小さい方の2つの数：-7 × -5 = 35

まとめ

この手法なら、配列をソートせずに1回の走査（O(n)）だけで最大積を求められます。ソート方式では O(n log n) の計算量が必要になるため、要素数の多いデータを扱う際には本アプローチの方がはるかに効率的です。負の数を含む配列でも正しく動作する点が実務上の大きな利点といえます。