C++で配列の最大積クアドラプル（サイズ4の部分列）を求める方法

問題の概要

本記事では、配列 arr[] が与えられたとき、その中から積が最大となる4つの要素（サイズ4の部分列＝クアドラプル）を見つけるプログラムをC++で実装する方法を解説します。

問題の説明：配列から任意の4つの要素を選び、それらの積が最大になる組み合わせを求めることが目的です。

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

入力

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

出力

480

説明

積が最大となるのは (-2, 5, -6, 8) の組み合わせで、(-2) × 5 × (-6) × 8 = 480 となります。負の数同士を掛けると正になるため、負の要素を含む組み合わせが最大になるケースが存在する点に注意が必要です。

解法アプローチ

この問題には複数の解き方があります。ここでは代表的な3つのアプローチを順に紹介します。

アプローチ1：全探索（ブルートフォース）

最もシンプルな方法は、配列を走査して取り得るすべての4つ組を列挙し、それぞれの積を計算して最大値を比較する方法です。

実装例：

#include <iostream>
using namespace std;
int max(int a, int b){
    if(a > b)
        return a;
        return b;
}
int findMaxProdQuad(int arr[], int n){
    int maxProd = 0;
    int prod = 1;
    for (int i = 0; i <= n - 4; i++)
    for (int j = i + 1; j <= n - 3; j++)
    for (int k = j + 1; k <= n - 2; k++)
    for (int l = k + 1; l <= n - 1; l++) {
        prod = arr[i] * arr[j] * arr[k] * arr[l];
        maxProd = max(maxProd, prod);
        prod = 1;
    }
    return maxProd;
}
int main(){
    int arr[] = {4, -2, 5, -6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
    return 0;
}

出力

Maximum product of quadruple is 480

この方法は直感的で理解しやすい反面、4重ループを使用するため時間計算量は O(n⁴) となり、配列が大きくなると非効率になります。

アプローチ2：最大値・最小値を追跡する方法

より効率的な方法として、配列内の大きい方から4つの要素（mx1〜mx4）と小さい方から4つの要素（mn1〜mn4）をそれぞれ求め、以下の3つの積を比較する方法があります。

1. mx1 × mx2 × mx3 × mx4（大きい正の数4つ）
2. mn1 × mn2 × mn3 × mn4（小さい負の数4つ）
3. mx1 × mx2 × mn1 × mn2（大きい正の数2つ＋小さい負の数2つ）

これら3つのうち最大の値を返すことで、あらゆるケースが網羅され、必ず最大積のクアドラプルが得られます。

実装例：

#include <iostream>
using namespace std;
int max(int a, int b){
    if(a > b)
        return a;
        return b;
}
int findMaxProdQuad(int arr[], int n) {
    int mx1 = -1000, mx2 = -1000, mx3 = -10000, mx4 = -1000;
    int mn1 = 1000, mn2 = 1000, mn3 = 1000, mn4 = 1000;
    for (int i = 0; i < n; i++) {
        if(arr[i] < mn1){
            mn4 = mn3;
            mn3 = mn2;
            mn2 = mn1;
            mn1 = arr[i];
        }
        else if(arr[i] < mn2){
            mn4 = mn3;
            mn3 = mn2;
            mn2 = arr[i];
        }
        else if(arr[i] < mn3){
            mn4 = mn3;
            mn3 = arr[i];
        }
        else if(arr[i] < mn4){
            mn4 = arr[i];
        }
        if(arr[i] > mx1){
            mx4 = mx3;
            mx3 = mx2;
            mx2 = mx1;
            mx1 = arr[i];
        }
        else if(arr[i] > mx2){
            mx4 = mx3;
            mx3 = mx2;
            mx2 = arr[i];
        }
        else if(arr[i] > mx3){
            mx4 = mx3;
            mx3 = arr[i];
        }
        else if(arr[i] > mx4){
            mx4 = arr[i];
        }
    }
    int maxVal = max ((mx1 * mx2 * mx3 * mx4), (mn1 * mn2 * mn3 * mn4));
    maxVal = max(maxVal, (mx1 * mx2 * mn1 * mn2));
    return maxVal;
}
int main() {
    int arr[] = {4, -2, 5, -6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
    return 0;
}

出力

Maximum product of quadruple is 480

この方法は配列を1回走査するだけで済むため、時間計算量は O(n) と非常に効率的です。

アプローチ3：ソートを利用する方法

配列をソートすると、最大の4要素は末尾に、最小の4要素は先頭に集まります。あとはアプローチ2と同じ要領で、3つの組み合わせの積を比較して最大値を求めます。

実装例：

#include <bits/stdc++.h>
using namespace std;
int findMaxProdQuad(int arr[], int n){
    sort(arr, arr + n);
    int maxVal = max((arr[n-1] * arr[n-2] * arr[n-3] * arr[n-4]), (arr[0] * arr[1] * arr[2] * arr[3]));
    maxVal = max(maxVal, (arr[n-1] * arr[n-2] * arr[0] * arr[1]));
    return maxVal;
}
int main(){
    int arr[] = {4, -2, 5, -6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
    return 0;
}

出力

Maximum product of quadruple is 480

ソートに O(n log n) の計算量を要しますが、コードが非常に簡潔になり、実装も容易なのが魅力です。

まとめ

配列から積が最大となる4つの要素を求める問題について、全探索（O(n⁴)）、最大・最小値の追跡（O(n)）、ソート（O(n log n)）の3つの解法を紹介しました。入力サイズやパフォーマンス要件に応じて、最適な手法を選択することが重要です。