C++で配列内の最大トリプレット合計を求める方法（i < j < k かつ a[i] < a[j] < a[k] の条件付き）

概要

サイズ n の正整数からなる配列が与えられたとき、0 <= i < j < k < n かつ a_i < a_j < a_k を満たすトリプレット（a_i + a_j + a_k）の中で最大の合計値を求めるのが本記事の課題です。

入力例

a[] = 3 6 4 2 5 10

出力例

19

説明

考えられるすべてのトリプレットは以下の通りです。
3 4 5 => 合計 = 12
3 6 10 => 合計 = 19
3 4 10 => 合計 = 17
4 5 10 => 合計 = 19
2 5 10 => 合計 = 17
最大合計 = 19

解法アプローチ

単純なアプローチ（ブルートフォース）

最もシンプルな方法は、3重の for ループですべてのトリプレットを順に調べ、それぞれの合計を計算して最大値を更新していくものです。しかし、この方法の時間計算量は O(n³) となるため、n が大きくなると実用性に欠けます。

改善されたアプローチ（O(n²)）

上記の方法をさらに最適化するために、3重ループの代わりに2重ループで走査する方法が有効です。

具体的には、各要素を「中央の要素（a_j）」とみなし、以下の手順で処理します。

• その要素より前にある要素の中から、a_j より小さい値の最大値（a_i）を求める。
• その要素より後ろにある要素の中から、a_j より大きい値の最大値（a_k）を求める。

両方が存在する場合のみ、合計 a_i + a_j + a_k を計算し、これまでの最大値と比較して答えを更新します。この方法の時間計算量は O(n²) であり、単純なアプローチよりも大幅に高速化できます。

C++による実装例

// C++プログラム：最大トリプレット合計を求める
#include <bits/stdc++.h>
using namespace std;

// 最大トリプレット合計を計算する関数
int maxTripletSum(int arr1[], int n1){
    // 答えを初期化
    int ans1 = 0;
    for (int i = 1; i < n1 - 1; ++i) {
        int max1 = 0, max2 = 0;
        // arr1[i] より小さい最大値を求める（0 ～ i-1 の範囲）
        for (int j = 0; j < i; ++j)
            if (arr1[j] < arr1[i])
                max1 = max(max1, arr1[j]);
        // arr1[i] より大きい最大値を求める（i+1 ～ n1-1 の範囲）
        for (int j = i + 1; j < n1; ++j)
            if (arr1[j] > arr1[i])
                max2 = max(max2, arr1[j]);
        // 左右どちらも候補が存在する場合のみ答えを更新
        if(max1 && max2)
            ans1 = max(ans1, max1 + arr1[i] + max2);
    }
    return ans1;
}

// ドライバーコード
int main(){
    int Arr[] = { 3, 6, 4, 2, 5, 10 };
    int N = sizeof(Arr) / sizeof(Arr[0]);
    cout << maxTripletSum(Arr, N);
    return 0;
}

実行結果

19

まとめ

この問題では、各要素を中央の要素として扱うことで、必要な探索範囲を左右に分割でき、計算量を O(n³) から O(n²) へ削減できます。さらに、前方向の最大値や後ろ方向の最大値を事前に配列へキャッシュしておくことで、追加の最適化も可能です。競技プログラミングやアルゴリズム学習において、こうした「中央要素固定」の発想は応用範囲が広いため、ぜひ覚えておきましょう。