C++で配列の最大積部分集合を求めるアルゴリズムと実装方法を解説

この問題では、n個の整数からなる配列 arr[] が与えられ、その中から部分集合を選んで積の最大値(最大積部分集合)を求めるプログラムを作成します。

問題の概要

配列の要素から任意の部分集合を選び、その積として考えられる最大値を計算します。

部分集合 − 配列 sub[] のすべての要素が配列 arr[] に含まれているとき、sub[] は arr[] の部分集合とみなされます。

具体例で問題を理解する

入力

arr[] = {4, 5, 2, -1, 3}

出力

40

説明

部分集合 sub[] = {4, 5, 2}
積 = 4 × 5 × 2 = 40

解法アプローチ

1. 単純な方法(全列挙)

最もシンプルなのは、配列のすべての部分集合を生成し、それぞれの積を計算して最大値を返す方法です。実装は容易ですが、ネストしたループが必要となり、計算量は O(n² × n) 程度に達します。nが大きくなると実用的ではありません。

2. 効率的な方法(負の数と0の個数を利用)

より効率的な解法は、配列内の負の数の個数(nofNeg)と0の個数(nof0)を数え、その条件に応じて最大積 maxProd を計算するものです。計算量は O(n) に抑えられます。

このアプローチのポイントは以下の通りです。

• 負の数を偶数個掛け合わせると結果は正になるため、負の数が偶数個ならすべての要素を掛け合わせるのが最適です。
• 負の数が奇数個の場合、絶対値が最小の負の数(0に最も近い負の数)を除外すると積が最大化されます。
• 0を掛けると積は0になるため、0は必ず積から除外します。

各ケースの詳細は以下の通りです。

• ケース1(nof0 = 0 かつ nofNeg が偶数)− 配列のすべての要素を積に含めます。
  maxProd = arr[0] × arr[1] × … × arr[n−1]
• ケース2(nof0 = 0 かつ nofNeg が奇数)− 0に最も近い負の数(絶対値が最小の負の数)を除くすべての要素を積に含めます。
• ケース3(nof0 ≠ 0)− すべての0を積から除外し、ケース1・2と同様の判定を行います。
• 特別なケース − 0以外の要素が1つだけで、それが負の数の場合は maxProd = 0 となります。

アルゴリズム

初期化 −

maxProd = 1;

ステップ1 −

配列を走査し、nof0(0の個数)と nofNeg(負の数の個数)を数えながら
maxProd を計算します。
maxProd = maxProd × arr[i]、i → 0 から n−1

ステップ2 −

以下のケースを判定します −
ケース1 − nofNeg % 2 == 0 の場合:maxProd をそのまま返す
ケース2 − nofNeg % 2 != 0 の場合:maxProd = maxProd / (最大の負の数)
ケース3 − nof0 == (n−1) かつ nofNeg == 1 の場合:maxProd = 0

ステップ3 −

maxProd を出力します。

実装例

上記の解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;

int findMaxSubsetProd(int arr[], int n){
    int larNeg = -1000;   // 0に最も近い負の数を保持
    int nofNeg = 0, Nof0 = 0;
    int maxProd = 1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0){
            Nof0++;
            continue;
        }
        else if (arr[i] < 0) {
            nofNeg++;
            if(larNeg < arr[i])
                larNeg = arr[i];
        }
        maxProd = maxProd * arr[i];
    }
    if(nofNeg % 2 == 0){
        return maxProd;
    }
    else if(nofNeg % 2 != 0)
        return (maxProd / larNeg);
    if(Nof0 == (n-1) and nofNeg == 1)
        return 0;
    return maxProd;
}

int main(){
    int arr[] = {4, -2, 5, -1, 3, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "配列の部分集合の最大積は " << findMaxSubsetProd(arr, n);
    return 0;
}

出力

配列の部分集合の最大積は 720

まとめ

配列の部分集合の最大積を求める問題は、負の数と0の個数に着目することで、全列挙の O(n² × n) から O(n) まで計算量を大幅に削減できます。負の数が偶数個なら全要素を掛け合わせ、奇数個なら絶対値が最小の負の数を除外する、というシンプルなルールで効率的に解けるのがポイントです。