Pythonで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] の場合を考えてみましょう。このとき、条件を満たすトリプルとその合計は以下のようになります。

• (3, 4, 5): 合計 = 12
• (3, 6, 10): 合計 = 19
• (3, 4, 10): 合計 = 17
• (4, 5, 10): 合計 = 19
• (2, 5, 10): 合計 = 17

したがって、最大値は 19 となります。

解法のアプローチ

この問題は、各要素を「中央の要素」として扱い、その左側にあるより小さい値の最大値と、右側にあるより大きい値の最大値を組み合わせることで解くことができます。具体的な手順は以下の通りです。

1. n を配列 A のサイズとし、結果を格納する res を 0 で初期化します。
2. i を 1 から n - 1 まで繰り返します(中央の要素の候補)。
   • first_max := 0、second_max := 0 で初期化します。
   • j を 0 から i - 1 まで繰り返し、A[j] < A[i] であれば first_max を更新します(左側の小さい値の最大)。
   • j を i + 1 から n - 1 まで繰り返し、A[j] > A[i] であれば second_max を更新します(右側の大きい値の最大)。
   • first_max と second_max がどちらも 0 以外の場合、res を first_max + A[i] + second_max の最大値で更新します。
3. 最後に res を返します。

このアルゴリズムの計算量は O(n²) であり、単純な全探索 O(n³) よりも効率的です。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

def get_max_triplet_sum(A):
    n = len(A)
    res = 0
    for i in range(1, (n - 1)):
        first_max = 0
        second_max = 0
        # 左側で A[i] より小さい値の最大を探す
        for j in range(0, i):
            if (A[j] < A[i]):
                first_max = max(first_max, A[j])
        # 右側で A[i] より大きい値の最大を探す
        for j in range((i + 1), n):
            if (A[j] > A[i]):
                second_max = max(second_max, A[j])
        # 両方が見つかった場合のみ合計を計算
        if (first_max and second_max):
            res = max(res, first_max + A[i] + second_max)
    return res

A = [3, 6, 4, 2, 5, 10]
print(get_max_triplet_sum(A))

入力

[3, 6, 4, 2, 5, 10]

出力

19

コードのポイント

• 中央要素の選択: ループ変数 i はトリプルの真ん中の要素を表します。範囲は 1 から n - 1 までで、左右に少なくとも1つずつ要素が必要なためです。
• first_max と second_max: 左側では A[i] より小さい最大値を、右側では A[i] より大きい最大値をそれぞれ記録します。これにより、合計が最大化されるトリプルを効率的に見つけられます。
• 存在チェック: first_max または second_max が 0 のままの場合、有効なトリプルが存在しないため、合計の計算をスキップします。

このように、各要素を基準点として左右の候補を管理することで、O(n²) の時間計算量で問題を解決できます。さらに効率化したい場合は、右側の最大値をあらかじめ suffix max 配列として計算しておき、左側の走査だけを行う O(n log n)〜O(n) の最適化も可能です。