C++で配列の最大積サブセットを求めるアルゴリズムと実装方法

このチュートリアルでは、配列の中から部分集合を選び、その積が最大になる値を求めるプログラムについて解説します。

ここでは、正の値と負の値が混在する配列が与えられます。私たちのタスクは、この配列の部分集合の中で積が最大となるものを見つけることです。

アルゴリズムの考え方

最大積を求めるための基本的な戦略は以下の通りです。

• 0は乗算に含めない：0を掛けると積が0になってしまうため、計算から除外します。
• 負の数の扱い：負の数が偶数個ある場合はすべて掛けて問題ありません。奇数個の場合は、絶対値が最も小さい（0に最も近い）負の数を除外することで、積を最大化できます。
• 全要素が0の場合：配列のすべての要素が0であれば、答えは0になります。
• 負の数が1つだけで残りが0の場合：正の積を作れないため、答えは0になります。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int maxProductSubset(int a[], int n) {
    // 要素が1つだけなら、その値が答え
    if (n == 1)
        return a[0];

    int max_neg = INT_MIN;          // 絶対値が最小の負の数
    int count_neg = 0, count_zero = 0;
    int prod = 1;

    for (int i = 0; i < n; i++) {
        // 0を掛けても意味がないのでスキップ
        if (a[i] == 0) {
            count_zero++;
            continue;
        }
        if (a[i] < 0) {
            count_neg++;
            max_neg = max(max_neg, a[i]);
        }
        prod = prod * a[i];
    }

    // すべての要素が0の場合
    if (count_zero == n)
        return 0;

    // 負の数が奇数個の場合
    if (count_neg & 1) {
        // 負の数が1つだけで、残りがすべて0の場合
        if (count_neg == 1 &&
            count_zero > 0 &&
            count_zero + count_neg == n)
            return 0;
        // 絶対値が最小の負の数を除外する
        prod = prod / max_neg;
    }
    return prod;
}

int main() {
    int a[] = { -1, -1, -2, 4, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << maxProductSubset(a, n);
    return 0;
}

出力

24

処理の流れの解説

上記の例では、配列 {-1, -1, -2, 4, 3} に対して処理を行っています。まず0以外の全要素の積を計算すると (-1) × (-1) × (-2) × 4 × 3 = -24 となります。負の数は3つ（奇数）なので、絶対値が最も小さい -1 を除外します。結果として -24 / (-1) = 24 が最大積として返されます。

このアルゴリズムは配列を一度走査するだけなので、時間計算量は O(n)、補助的な記憶領域は O(1) で済み、非常に効率的です。