C++で配列の最大トリプレット和を求める方法【初心者向け解説】

この記事では、与えられた配列の中から3つの要素を選んだときの合計（トリプレット和）が最大になる組み合わせを見つけるプログラムをC++で作成します。

問題の概要

配列が与えられたとき、その中から3つの要素を選び、その合計が最大となる組み合わせを求めるのが課題です。

具体例で理解しよう

入力： array = {4, 6, 1, 2}

出力： 12

解説：

すべてのトリプレットの組み合わせ：
(4, 6, 1) = 4 + 6 + 1 = 11
(4, 6, 2) = 4 + 6 + 2 = 12
(4, 1, 2) = 4 + 1 + 2 = 7
(6, 1, 2) = 6 + 1 + 2 = 9

最大トリプレット和は 12

方法1：全探索（ブルートフォース）によるアプローチ

最もシンプルな方法は、上記の例のようにすべてのトリプレットの組み合わせについて合計を計算し、その中から最大値を見つけることです。

具体的には、3重ループを回して考えられるすべてのトリプレット和を求め、現在の最大値（maxSum）よりも大きければ更新していきます。

ただし、この方法の計算量は O(n³) となるため、配列の要素数が大きくなると処理時間が急激に増加し、実用的ではありません。

サンプルコード

#include <iostream>
using namespace std;

int maxSum(int arr[], int n){
    int maxSum = 0;
    int i, j, k;
    // すべてのトリプレットの組み合わせを調べる
    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++)
            for (k = j + 1; k < n; k++)
                if (maxSum < arr[i] + arr[j] + arr[k])
                    maxSum = arr[i] + arr[j] + arr[k];
    return maxSum;
}

int main(){
    int arr[] = { 3, 5, 7, 1, 9, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "配列の最大トリプレット和は " << maxSum(arr, n);
    return 0;
}

実行結果

配列の最大トリプレット和は 21

方法2：ソートを活用した効率的なアプローチ

より効率的な方法は、まず配列を昇順にソートし、末尾（最大値側）の3つの要素の合計を返すというものです。

ソート後の配列では最も大きい3つの要素が末尾に集まるため、それらの合計が必然的に最大トリプレット和となります。計算量は O(n log n) に抑えられ、全探索と比べて大幅に高速です。

サンプルコード

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

int maxSum(int arr[], int n) {
    // 配列を昇順にソート
    sort(arr, arr + n);
    // 最大の3要素の合計を返す
    return arr[n - 1] + arr[n - 2] + arr[n - 3];
}

int main() {
    int arr[] = { 3, 5, 9, 1, 2, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "配列の最大トリプレット和は " << maxSum(arr, n);
    return 0;
}

実行結果

配列の最大トリプレット和は 24

まとめ

実務や競技プログラミングでは、ソートを利用した方法2のアプローチを採用するのがベストです。なお、負の数を含む配列にも対応させたい場合は、初期値 maxSum を INT_MIN など適切な最小値で初期化することをおすすめします。