C++で配列をk回繰り返して作った配列の最大部分配列和を求める方法

問題概要

この問題では、1つの配列と整数 k が与えられます。与えられた配列を k 回繰り返してできる新しい配列の中から、最大部分配列和(連続する要素の合計の最大値)を求めるプログラムを C++ で作成します。

具体例で確認してみましょう。

入力: array = {3, 5, 1}、k = 2

出力: 18

説明:

配列を2回繰り返すと、
array = {3, 5, 1, 3, 5, 1}
最大部分配列和 = 3+5+1+3+5+1 = 18

解法のアプローチ

この問題を効率的に解くポイントは、元の配列の全要素の合計(arraySum)を先に計算し、その符号によって場合分けすることです。

• arraySum > 0 の場合: 配列全体の合計が正であるため、繰り返し回数が増えるほど部分配列和も大きくなります。よって、「2回繰り返した配列から得られる最大部分配列和 + (k − 2) × arraySum」が答えになります。
• arraySum ≤ 0 の場合: 配列全体の合計が正でない場合、それ以上繰り返しても合計は増えません。そこで、2回繰り返した配列に対して最大部分配列和を求めたものがそのまま答えになります。

なお、最大部分配列和の計算にはカダネのアルゴリズム(Kadane's algorithm)を使用します。これにより O(n) の計算量で効率的に求められます。

アルゴリズムの手順

1. 元の配列の全要素の合計 arraySum を計算する。
2. 元の配列を2回繰り返した配列 b を作成する(k ≥ 2 の場合、最大部分配列は高々2周期分にまたがるだけで十分なため)。
3. 配列 b に対してカダネのアルゴリズムで最大部分配列和を求める。
4. arraySum > 0 ならば、3の結果に (k − 2) × arraySum を加算して返す。

C++での実装例

#include<iostream>
using namespace std;

// 配列arrをk回繰り返して配列bにコピーする関数
void repeatArray(int *arr, int *b, int k, int len) {
    int j = 0;
    while (k > 0){
        for (int i = 0; i < len; i++)
            b[j++] = arr[i];
        k--;
    }
}

// カダネのアルゴリズムで最大部分配列和を求める関数
long subArraySum(int *a, int len) {
    int max = 0;
    long newmax = 0;
    for (int i = 0; i < len; i++) {
        newmax = newmax + a[i];
        if (max < newmax)
            max = newmax;
        if (newmax < 0)
            newmax = 0;
    }
    return max;
}

// 繰り返し後の配列における最大部分配列和を求める関数
long findMaxSubArraySum(int *arr, int k, int len) {
    int arraySum = 0;
    long maxSum = 0;
    int b[(2 * len)] = {0};
    repeatArray(arr, b, 2, len);
    for (int i = 0; i < len; i++)
        arraySum += arr[i];
    maxSum = subArraySum(b, 2*len);
    if (arraySum > 0)
        maxSum = subArraySum(b, 2*len) + (k - 2) * arraySum;
    return maxSum;
}

int main() {
    int arr[] = { 3, 5, 1};
    int length = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout << "The maximum subarray sum in array formed by repeating the given array "
         << k << " times is " << findMaxSubArraySum(arr, k, length);
    return 0;
}

出力結果

The maximum subarray sum in array formed by repeating the given array 3 times is 27

この例では、配列 {3, 5, 1}(合計9)を3回繰り返すため、2周期分の最大部分配列和「9」に (3 − 2) × 9 = 9 を加えた27が出力されます。

まとめ

配列を k 回繰り返した配列の最大部分配列和を求める問題は、配列全体の総和の符号で場合分けし、2周期分の配列に対してカダネのアルゴリズムを適用することで、実際に長大な配列を生成することなく効率的に解くことができます。計算量は元の配列のサイズ n に対して O(n) となり、k が非常に大きい場合でも高速に動作します。