C++でmを法とする最大部分配列の総和を求めるアルゴリズム

C++でmを法とする最大部分配列の総和とは

この問題では、サイズnの整数型配列と整数mが与えられます。求めるのは、すべての部分配列の総和の中から、mで割った余りが最大となる値です。

問題の概要 − 各部分配列の全要素の合計をmで割った余りを計算し、その中で最大の値を求めます。

具体例で問題を確認しよう

まずは例を見て、問題の内容を理解しましょう。

入力 − array = {4, 9, 2}、m = 6

出力 − 5

説明 − すべての部分配列と、それぞれを6で割った余りは以下の通りです。

{4}: 4 % 6 = 4
{9}: 9 % 6 = 3
{2}: 2 % 6 = 2
{4, 9}: 13 % 6 = 1
{9, 2}: 11 % 6 = 5
{4, 9, 2}: 15 % 6 = 3

この結果から、部分配列{9, 2}の総和11を6で割った余り「5」が最大値であることがわかります。

解法のアプローチ

この問題を効率的に解くには、累積和のmod配列(prefixSumModulo)を利用します。インデックスiまでの累積和をprefix[i]とするとき、任意の部分配列の総和の剰余は次の式で表せます。

(prefix[i] − prefix[j] + m) % m(ここで j < i)

ポイントは、prefix[i]より大きい最小のprefix[j]を見つけられれば、余りが最大に近づくという性質です。そこでstd::setを使ってこれまでの累積和(mod m)をソート済みの状態で管理し、lower_bound関数によってprefix[i] + 1以上の最小値を高速に探索します。これにより、全体の時間計算量はO(n log n)に抑えられます。

実装例

上記の解法を実装したC++プログラムがこちらです。

#include<bits/stdc++.h>
using namespace std;
int calcMaxSum(int arr[], int n, int m) {
    int x, prefix = 0, maxSumMod = 0;
    set<int> sums;
    sums.insert(0);
    for (int i = 0; i < n; i++){
        prefix = (prefix + arr[i])%m;
        maxSumMod = max(maxSumMod, prefix);
        auto it = sums.lower_bound(prefix+1);
        if (it != sums.end())
            maxSumMod = max(maxSumMod, prefix - (*it) + m );
        sums.insert(prefix);
    }
    return maxSumMod;
}
int main() {
    int arr[] = {4, 9, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int m = 5;
    cout<<"Maximum subarray sum modulo "<<m<<" is "<<calcMaxSum(arr, n, m) << endl;
    return 0;
}

実行結果

Maximum subarray sum modulo 5 is 4

このプログラムではm = 5として計算しています。配列{4, 9, 2}の各部分配列の総和を5で割った余りのうち最大となるのは、{4}または{9}による「4」であり、正しく出力されています。

まとめ

mを法とする最大部分配列の総和の問題は、単純な全探索ではO(n²)の計算量が必要ですが、累積和のmodとstd::set(平衡二分木)を組み合わせることで、O(n log n)まで高速化できます。剰余演算を含む区間和の最大化問題に直面した際は、「prefix[i]より大きい最小のprefix[j]を探す」という発想が非常に有効なので、ぜひ覚えておきましょう。