C++で配列の最大平衡和（イクリブリアム・サム）を求める方法

問題概要

配列 arr[] が与えられたとき、あるインデックス i における「接頭辞和（プレフィックスサム）」と「接尾辞和（サフィックスサム）」が一致する値の中から、最大値を見つけるのがこの問題の目的です。この一致する値は「平衡和（イクリブリアム・サム）」と呼ばれます。

例

入力配列が以下の場合を考えてみましょう。

Arr[] = {1, 2, 3, 5, 3, 2, 1}

このとき出力は 11 になります。その理由は次の通りです。

• 接頭辞和 = arr[0..3] = 1 + 2 + 3 + 5 = 11
• 接尾辞和 = arr[3..6] = 5 + 3 + 2 + 1 = 11

インデックス 3 を境にして、左側の要素の合計と右側の要素の合計がどちらも 11 となり、これが最大の平衡和です。

アルゴリズム

この問題は、前からの累積和と後ろからの累積和をそれぞれ配列に記録して比較するというシンプルなアプローチで解けます。

• まず配列を先頭から順に走査し、各インデックスの接頭辞和を presum[] 配列に格納します。presum[i] には部分配列 arr[0..i] の合計が入ります。
• 次に配列を末尾から再度走査し、接尾辞和を別の配列 suffsum[] に格納します。suffsum[i] には部分配列 arr[i..n-1] の合計が入ります。
• 各インデックス i について presum[i] と suffsum[i] が等しいかどうかを確認し、等しければそれまでの全体最大値と比較して、より大きい方を結果として保持します。

この手法の計算量は時間 O(n)、空間 O(n) であり、配列を2回走査するだけで済むため非常に効率的です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
    int preSum[n];
    int suffSum[n];
    int result = INT_MIN;
    preSum[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        preSum[i] = preSum[i - 1] + arr[i];
    }
    suffSum[n - 1] = arr[n - 1];
    if (preSum[n - 1] == suffSum[n - 1]) {
        result = max(result, preSum[n - 1]);
    }
    for (int i = n - 2; i >= 0; --i) {
        suffSum[i] = suffSum[i + 1] + arr[i];
        if (suffSum[i] == preSum[i]) {
            result = max(result, preSum[i]);
        }
    }
    return result;
}
int main() {
    int arr[] = {1, 2, 3, 5, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max equlibrium sum = " << getMaxSum(arr, n) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Max equlibrium sum = 11

まとめ

接頭辞和と接尾辞和をあらかじめ計算しておくことで、任意のインデックスにおける平衡点の判定を即座に行えるようになります。平衡和が存在しない場合、関数は INT_MIN を返すため、実際の利用時には戻り値のチェックを行うと安全です。また、空間計算量を削減したい場合は、総和を先に求めておき、走査しながら差分から接尾辞和を導出する方法で O(1) の追加メモリに抑えることも可能です。