JavaScriptで最大積となる部分配列を求めるアルゴリズム

問題概要

JavaScriptで、整数(正と負の両方)を含む配列を唯一の引数として受け取る関数を書く必要があります。この関数は、配列内の連続した要素からなる部分配列のうち、積が最大になるものを見つけ出し、その積を返します。

例えば、次のような入力配列が与えられたとします。

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

この場合、出力は次のようになります。

const output = 120

これは、部分配列 [4, -5, 2, -3] の積が 4 × (-5) × 2 × (-3) = 120 となり、これがすべての部分配列の中で最大の積だからです。負の数が偶数個含まれることで、マイナス同士が打ち消し合い、大きな正の値が生まれています。

解決策の考え方

この問題は動的計画法(DP)を使って効率的に解けます。ポイントは、各位置で「現在位置で終わる部分配列の最大積」と「最小積」の両方を追跡することです。負の数を掛けると最大と最小が入れ替わる可能性があるため、最小値も記録しておく必要があります。

具体的には、各要素について以下の3つの候補の最大値を新たな最大積とし、同様に3つの候補の最小値を新たな最小積として更新していきます。

• 現在の要素そのもの
• 現在の要素 × これまでの最大積
• 現在の要素 × これまでの最小積

そして、更新された最大積の履歴全体の中で最も大きい値を答えとして返します。

実装コード

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

const arr = [4, -5, 2, -3, 1, -4, 0, -3];
const maxProduct = (arr = []) => {
    if (arr.length === 0){
        return 0;
    };
    let max = arr[0],
    min = arr[0],
    greatest = arr[0];
    for (let i = 1; i <= arr.length - 1; i++) {
        let tempMax = max * arr[i];
        max = Math.max(
            arr[i],
            Math.max(min * arr[i], max * arr[i])
        );
        min = Math.min(arr[i], Math.min(min * arr[i], tempMax));
        greatest = Math.max(greatest, max);
    }
    return greatest;
};
console.log(maxProduct(arr));

コードの解説

まず、配列が空の場合は 0 を返すガード節を設けています。初期状態では、最初の要素を最大積(max)、最小積(min)、そして全体の答え(greatest)として設定します。

ループ内では、先に tempMax として「旧max × 現在の要素」を保存しておくのが重要です。これは、max を更新してしまうと、直後の min の計算で古い最大積が使えなくなるためです。

各ループの最後で greatest を更新することで、途中のどの時点で最大積が現れても見逃さないようになっています。

出力結果

コンソールの出力は次の通りです。

120

計算量

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加の記憶領域は定数個の変数のみなので空間計算量は O(1) となります。全ての部分配列を総当たりで調べる O(n²) や O(n³) の素朴な手法に比べて、非常に効率的です。