C++で配列から4つの要素を選んだ最大積を求める方法

n個の整数が格納された配列が与えられたとき、その中から4つの要素を選んで作れる積（クアドラプル）の最大値を求める問題について解説します。

例えば、配列が [3, 5, 20, 6, 10] の場合、最大積は 6000 となり、このとき選ばれる4つの要素は 10, 5, 6, 20 です。

解法のアプローチ

この問題は、配列をソートすることで効率的に解くことができます。最大積の候補として考えられるのは以下の3パターンだけです。

• 配列を昇順にソートする
• x = 最後の4要素（最も大きい4つ）の積とする
• y = 最初の4要素（最も小さい4つ）の積とする
• z = 最初の2要素と最後の2要素の積とする

x、y、z のうち最大のものを返せば答えになります。

なぜ3パターンだけで十分なのか

負の数が含まれる場合に注意が必要です。負の数同士を掛けると正になるため、「最も小さい（絶対値の大きい負の）2つ」と「最も大きい2つ」を掛け合わせた組み合わせが最大になる可能性があります。上記の3パターンを比較すれば、正の数のみの場合も負の数が混在する場合もすべてカバーできます。

C++での実装例

#include<iostream>
#include<algorithm>
using namespace std;

int maxQuadProduct(int arr[], int n) {
    if (n < 4)
        return -1;
    sort(arr, arr + n);
    int last_four = arr[n - 1] * arr[n - 2] * arr[n - 3] * arr[n - 4];
    int first_four = arr[0] * arr[1] * arr[2] * arr[3];
    int two_first_last = arr[0] * arr[1] * arr[n - 1] * arr[n - 2];
    return max(last_four, max(first_four, two_first_last));
}

int main() {
    int arr[] = { -10, -3, 5, 6, -20 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int maximum_val = maxQuadProduct(arr, n);
    if (maximum_val == -1)
        cout << "No Quadruple Exists";
    else
        cout << "Maximum product is " << maximum_val;
}

実行結果

Maximum product is 6000

コードのポイント

• 要素数が4未満の場合はクアドラプルが存在しないため、-1 を返してエラー扱いにしています。
• std::sort によるソートの計算量は O(n log n) であり、全組み合わせを調べる O(n⁴) の総当たり方式より大幅に効率的です。
• サンプル入力 { -10, -3, 5, 6, -20 } では、最初の2要素（-20 × -10 = 200）と最後の2要素（5 × 6 = 30）の積である 200 × 30 = 6000 が最大となり、z のパターンが採用される好例です。