C++で配列をK回連結した後に作成される配列の最大サブ配列合計を求める方法

このチュートリアルでは、配列を繰り返し連結して作成される配列における最大サブ配列合計（Maximum Subarray Sum）を求めるC++プログラムについて解説します。

具体的には、1つの配列と整数Kが与えられ、元の配列をK回繰り返して連結した配列の中から、要素の合計が最大となる連続する部分配列（サブ配列）を見つけることが課題となります。

アルゴリズムのポイント

この問題は、有名なカダネのアルゴリズム（Kadane's Algorithm）を応用することで効率的に解けます。

• ループは n * k 回実行します（連結後の配列全体を走査）。
• a[i % n] のように剰余演算を使うことで、実際に大きな配列を作成せずとも、元の配列を循環的に参照できます。
• max_ending_here は現在注目している部分配列の合計を保持し、負になった時点で0にリセットします。
• max_so_far はこれまでに見つかった最大合計を記録していきます。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
// 最大サブ配列の合計を返す関数
int maxSubArraySumRepeated(int a[], int n, int k) {
    int max_so_far = INT_MIN, max_ending_here = 0;
    for (int i = 0; i < n*k; i++) {
        max_ending_here = max_ending_here + a[i%n];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if (max_ending_here < 0) max_ending_here = 0;
    }
    return max_so_far;
}
int main() {
    int a[] = {10, 20, -30, -1};
    int n = sizeof(a)/sizeof(a[0]);
    int k = 3;
    cout << "Maximum contiguous sum is "
        << maxSubArraySumRepeated(a, n, k);
    return 0;
}

実行結果

Maximum contiguous sum is 30

上記の例では、配列 {10, 20, -30, -1} を3回連結すると {10, 20, -30, -1, 10, 20, -30, -1, 10, 20, -30, -1} となります。この中で合計が最大となる連続部分配列は {10, 20} であり、その合計 30 が出力されます。

このように、剰余演算による循環参照を利用すれば、連結後の巨大な配列を実際にメモリ上に構築することなく、時間計算量 O(n×k) で最大サブ配列合計を求めることができます。