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

この記事では、n個の整数からなる配列arr[]が与えられたとき、その中から3つの要素（サイズ3の部分列＝トリプレット）を選び、積が最大となる組み合わせを見つけて、その最大積を返す方法を解説します。

問題例

入力

arr[] = {9, 5, 2, 11, 7, 4}

出力

693

説明

配列全体の中で最も大きな積となるトリプレットは「9 × 11 × 7」であり、その積は693となります。

解法アプローチ

この問題には複数の解き方が存在します。ここでは代表的な3つの手法を、アルゴリズムと実装例とともに紹介します。

方法1：全探索（ブルートフォース）

最もシンプルな方法です。配列を三重ループで走査し、考えられるすべてのトリプレットの組み合わせについて積を計算し、その中で最大のものを返します。時間計算量はO(n³)となるため、大規模な配列には不向きです。

アルゴリズム

初期化：

maxProd = −1000

ステップ1：

3つのネストしたループを作成：
ループ1：i → 0 から n−3
ループ2：j → i+1 から n−2
ループ3：k → j+1 から n−1

ステップ1.1：

積を計算：prod = arr[i] * arr[j] * arr[k]

ステップ1.2：

if prod > maxProd → maxProd = prod

ステップ3：

maxProd を返す。

実装例

#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
    int maxProd = -1000;
    int prod;

    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++){
        prod = arr[i] * arr[j] * arr[k];
        if(maxProd < prod)
        maxProd = prod;
    }
    return maxProd;
}
int main(){
    int arr[] = { 9, 5, 2, 11, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
    return 0;
}

出力

Maximum product of a triplet in array is 693

方法2：ソートを利用する

この方法では、まず配列を降順にソートします。ソート後の配列において、最大積となるトリプレットの候補は次の2つです。

(arr[0], arr[1], arr[2])      // 上位3つの要素
(arr[0], arr[n−1], arr[n−2])  // 最大値と最小値2つ

負の数が含まれる場合、「最小値 × 2番目に小さい値 × 最大値」が最大になる可能性があるため、両方の候補を比較して大きい方を返します。時間計算量はO(n log n)です。

アルゴリズム

ステップ1：

与えられた配列を降順にソートする。

ステップ2：

トリプレットの積を計算：
maxTriplet1 = arr[0]*arr[1]*arr[2]
maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]

ステップ3：

if(maxTriplet1 > maxTriplet2) → return maxTriplet1

ステップ4：

else → return maxTriplet2

実装例

#include <bits/stdc++.h>
using namespace std;
int calcMaxProd(int arr[], int n){
    sort(arr, arr + n, greater<>());
    int maxTriplet1 = arr[0]*arr[1]*arr[2];
    int maxTriplet2 = arr[0]*arr[n-1]*arr[n-2];
    if(maxTriplet1 > maxTriplet2)
        return maxTriplet1;
    return maxTriplet2;
}
int main(){
    int arr[] = { 9, 5, 2, 11, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximum product of a triplet in array is "
    <<calcMaxProd(arr, n);
    return 0;
}

出力

Maximum product of a triplet in array is 693

方法3：1回の走査で必要な値を見つける（最適解）

最大積となるトリプレットは、次の2つのパターンのいずれかであることが分かっています。

(最大値, 2番目に大きい値, 3番目に大きい値)
(最大値, 最小値, 2番目に小さい値)

そこで、配列を1回だけ走査して上位3つの値と下位2つの値を直接求め、それらを使って最大積を計算します。ソートが不要なため、時間計算量はO(n)と、3つの方法の中で最も効率的です。

アルゴリズム

初期化：

max = −1000, secMax = −1000, thirdMax = −1000
min = 10000, secMin = 10000

ステップ1：

配列を i → 0 から n−1 までループする。

ステップ1.1：

if(arr[i] > max) → thirdMax = secMax, secMax = max, max = arr[i]

ステップ1.2：

elseif(arr[i] > secMax) → thirdMax = secMax, secMax = arr[i]

ステップ1.3：

elseif(arr[i] > thirdMax) → thirdMax = arr[i]

ステップ1.4：

if(arr[i] < min) → secMin = min, min = arr[i]

ステップ1.5：

elseif(arr[i] < secMin) → secMin = arr[i]

ステップ2：

triplet1 = max * secMax * thirdMax
triplet2 = max * min * secMin

ステップ3：

if(triplet1 > triplet2) → return triplet1

ステップ4：

else → return triplet2

実装例

#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
    int max = -1000, secMax = -1000, thirdMax = -1000;
    int min = 1000, secMin = 1000;
    for (int i = 0; i < n; i++){
        if (arr[i] > max){
            thirdMax = secMax;
            secMax = max;
            max = arr[i];
        }
        else if (arr[i] > secMax){
            thirdMax = secMax;
            secMax = arr[i];
        }
        else if (arr[i] > thirdMax)
        thirdMax = arr[i];
        if (arr[i] < min){
            secMin = min;
            min = arr[i];
        }
        else if(arr[i] < secMin)
        secMin = arr[i];
    }
    int triplet1 = max * secMax * thirdMax;
    int triplet2 = max * secMin * min;
    if(triplet1 > triplet2)
    return triplet1;
    return triplet2;
}
int main(){
    int arr[] = { 9, 5, 2, 11, 7, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximum product of a triplet in array is "
    <<calcMaxProd(arr, n);
    return 0;
}

出力

Maximum product of a triplet in array is 693

まとめ：各手法の計算量比較

配列のサイズが大きくなるほど、方法3のような線形時間のアプローチが有利になります。ただし、初期化時の最小値・最大値の設定値は、扱うデータの範囲に応じて適切に調整してください。