C++で2回の走査を用いて最大積部分配列（Maximum Product Subarray）を求める方法

この問題では、整数型の配列 arr[] が与えられます。求められているのは、C++において「2回の走査（Two Traversals）」を利用して最大積部分配列（Maximum Product Subarray）を求めるプログラムです。

問題の説明 − 配列の中から最大の積を持つ部分配列を見つけます。具体的には、インデックス0から開始する「左から右への走査」と、インデックス(n-1)から開始する「右から左への走査」という2方向のトラバーサルを組み合わせて解を導き出します。

具体例で問題を確認してみましょう。

入力

arr[] = {4, -2, 5, -6, 0, 8}

出力

240

解説

部分配列 = {4, -2, 5, -6}
最大積 = 4 × (-2) × 5 × (-6) = 240

負の数が偶数個含まれるため、それらを掛け合わせることで積が正になり、結果的に最大値240が得られています。

解法アプローチ

この問題は、2回の走査によって効率よく解くことができます。

• 1回目の走査：インデックス0からn-1へ向かう「左から右」の走査を行い、途中の累積積を計算します。積が0になった場合はリセットして1に戻します。
• 2回目の走査：インデックスn-1から0へ向かう「右から左」の走査を行い、同様に累積積を計算します。
• 最後に、両方向で得られた累積積のうち大きい方を最大値として返します。

このアプローチのポイントは、負の数の影響が配列のどちら側にあるかによって最大積の位置が変わる点を、左右両方向からの走査でカバーできることです。それ以外の考え方は、通常の最大積部分配列を求める手法と同じです。

ソリューションの動作を示すサンプルプログラム：

コード例

#include<iostream>
using namespace std;
int CalcMaxProductSubArray(int arr[], int n) {
    int frntMax = 1, rearMax = 1, maxVal = 1;
    for (int i=0; i<n; i++) {
        frntMax = frntMax*arr[i];
        if (frntMax == 0)
            frntMax = 1;
    }
    for (int i=n-1; i>=0; i--) {
        rearMax = rearMax * arr[i];
        if (rearMax == 0)
            rearMax = 1;
    }
    maxVal = max(frntMax, rearMax);
    return maxVal;
}
int main() {
    int arr[] = {4, -2, 5, -6, 0, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Maximum product subarray is "<<CalcMaxProductSubArray(arr, n);
    return 0;
}

出力

Maximum product subarray is 240

このように、配列を前後の2方向から一度ずつ走査するだけで、最大積部分配列の積を求めることができます。時間計算量はO(n)、空間計算量はO(1)であり、非常にシンプルかつ効率的な実装となっています。