C++で配列内のトリプレット（サイズ3の部分列）の最大積を求める方法

このチュートリアルでは、配列の中から選んだ3つの要素（サイズ3の部分列＝トリプレット）の積が最大となる組み合わせを求めるC++プログラムについて解説します。

具体的には、整数の配列が与えられ、その中から積が最大になる3要素の組み合わせを見つけるのが課題です。たとえば、配列 {10, 3, 5, 6, 20} の場合、10 × 6 × 20 = 1200 が最大の積となります。

アプローチ：全組み合わせの走査（ブルートフォース法）

最も基本的な方法は、3重のループで配列内のすべての3要素の組み合わせを調べることです。この方法は直感的で実装も簡単ですが、時間計算量が O(n³) と大きくなる点には注意が必要です。

処理の流れ

• 配列の要素数が3未満の場合はトリプレットが存在しないため、-1 を返します。
• 最大積を格納する変数を INT_MIN（int型が取り得る最小値）で初期化します。
• 3重ループによって i < j < k を満たすすべての組み合わせの積を計算し、それまでの最大値より大きければ更新します。

サンプルコード

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

// 最大積を求める関数
int maxProduct(int arr[], int n){
    if (n < 3)
        return -1;
    int max_product = INT_MIN;
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
            for (int k = j + 1; k < n; k++)
                max_product = max(max_product, arr[i] * arr[j] * arr[k]);
    return max_product;
}

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

※ 元のコードでは結果を受け取る変数名として max を使っていますが、標準ライブラリの std::max と紛らわしいため、ここでは result に変更しています。

実行結果

Maximum product is 1200

配列 {10, 3, 5, 6, 20} の中で最も大きな積を持つ組み合わせは 10 × 6 × 20 であり、実行すると 1200 が出力されます。

補足：より効率的なアプローチ

ブルートフォース法は O(n³) の計算量がかかるため、要素数の多い配列には不向きです。パフォーマンスを改善したい場合は、以下の方法が有効です。

• ソートを利用する方法： 配列をソートした後、「最大の3要素の積」と「最小の2要素 × 最大要素の積」を比較し、大きい方を答えとします。計算量は O(n log n) に抑えられます。
• 1回の走査で求める方法： ループを1回だけ回しながら、上位3つの最大値と下位2つの最小値を追跡すれば、O(n) で求めることも可能です。

特に負の値が含まれる配列では、「最小の2つの負の数 × 最大の正の数」の積が最大になるケースがあるため、複数の候補を必ず比較するようにしましょう。