最大積部分配列を求める|C++で負の数を含むケースに対応

この問題では、正の整数と負の整数が混在する配列が与えられます。C++を用いて、配列の中から積が最大となる部分配列(Maximum Product Subarray)を計算するプログラムを作成することが課題です。

問題の概要 − 扱う配列には、正の数・負の数・0が含まれています。配列の要素から作られる部分配列(連続する要素の集まり)の積を求め、その積が最大になる組み合わせを見つける必要があります。

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

入力

arr[] = {-1, 2, -7, -5, 12, 6}

出力

5040

説明

積が最大となる部分配列は {2, -7, -5, 12, 6} です。

積 = 5040

解法のアプローチ

この問題を解くには、現在の要素までの最大積を記録する maxVal と、積の最小値(負の極大値)を記録する minVal の2つの値を管理します。そして、現在読み込んだ要素の値に応じて、次のように両者を更新していきます。

ケース1 - 要素が正の数の場合 − 現在の要素を掛け合わせて maxVal と minVal を更新します。正の数は積を増加させる方向に働くためです。

ケース2 - 要素が0の場合 − 0を掛けると結果が必ず0になってしまうため、そこで現在の部分配列を打ち切り、新たな部分配列としてやり直します。

ケース3 - 要素が負の数の場合 − 負の数を掛けると符号が反転するため、それまでの最大値と最小値を入れ替えて更新します。小さかった値が掛け算によって最大値になり得るからです。

この解法の動作を示すプログラム

サンプルコード

#include <iostream>
using namespace std;
int min(int a, int b){
    if(a < b)
        return a;
        return b;
}
int max(int a, int b){
    if(a > b)
        return a;
        return b;
}
int CalcMaxProductSubArray(int arr[], int n) {
    int i = 0;
    int maxVal = -1000;
    int localMax = 1;
    int localMin = 1;
    int lastMax;
    while(i < n) {
        int currentVal = arr[i];
        if (currentVal > 0) {
            localMax = (localMax * currentVal);
            localMin = min(1, localMin * currentVal);
        }
        else if (currentVal < 0) {
            lastMax = localMax;
            localMax = (localMin * currentVal);
            localMin = (lastMax * currentVal);
        } else {
            localMin = 1;
            localMax = 0;
        }
        maxVal = max(maxVal, localMax);
        if (localMax <= 0)
            localMax = 1;
            i++;
    }
    return maxVal;
}
int main(){
    int arr[] = { -1, 2, -7, -5, 12, 6 };
    int n = 6;
    cout<<"最大積部分配列は "<<CalcMaxProductSubArray(arr, n);
    return 0;
}

実行結果

最大積部分配列は 5040