C++で解く！配列をk回連結した後に作成される配列の最大部分配列合計の求め方

この記事では、サイズnの配列arr[]と整数kが与えられたとき、配列をk回繰り返し連結して作成される新しい配列から、最大部分配列の合計を求めるプログラムをC++で実装する方法を解説します。

問題の概要

元の配列arr[]をk回繰り返して連結することで新しい配列を作成し、その中で合計値が最大となる部分配列（連続する要素の集まり）を見つけ、その合計を求めるのが目的です。

入出力例

具体的な例を使って問題を確認してみましょう。

入力

arr[] = {-9, -5, 14, 6}、k = 2

出力

26

説明

繰り返し連結後の新しい配列 : {-9, -5, 14, 6, -9, -5, 14, 6}
最大合計を持つ部分配列 = {14, 6, -9, -5, 14, 6}
合計 = 26

この例では、連結後の配列の中で「14, 6, -9, -5, 14, 6」を選んだときに合計26となり、これが最大値になります。

解法アプローチ1：シンプルな方法（Kadaneのアルゴリズム）

最も直感的な解法は、まずarr[]をk回連結した新しい配列を実際に作成し、その配列に対して最大部分配列合計を求めることです。この場合、Kadaneのアルゴリズムを使うのが最も効率的です。

Kadaneのアルゴリズムは、累積和が負になった時点でリセットすることで、線形時間O(n)で最大部分配列合計を求められる有名な手法です。

サンプルコード

#include <iostream>
using namespace std;

int calcMaxSubArraySum(int arr[], int n, int k){
    int newArr[2*n];
    for(int i = 0; i < k*n; i++)
        newArr[i] = arr[i%n];
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k*n; i++) {
        sum = sum + newArr[i];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main(){
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"繰り返し連結後に作成された配列の最大部分配列合計は "<<calcMaxSubArraySum(arr, n, k);
    return 0;
}

出力

繰り返し連結後に作成された配列の最大部分配列合計は 26

この方法でも正しく結果を得られますが、実際に大きな配列を生成するため、メモリ使用量や処理時間の面で非効率になる可能性があります。

解法アプローチ2：剰余演算を使った効率的な方法

より効率的に問題を解くには、剰余演算（モジュロ演算）を活用します。剰余演算とは、モジュロ演算子「%」を使って除算の余りを求める演算のことです。

ポイントは、連結後の配列のi番目の要素は、実は元の配列の「i % n」番目の要素と同じであるという性質です。この性質を利用すれば、新しい配列を実際に作成せずに、インデックスを剰余演算で変換しながら直接Kadaneのアルゴリズムを適用できます。

サンプルコード

#include <iostream>
using namespace std;

int calcMaxSubArraySum(int arr[], int n, int k){
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k*n; i++) {
        sum = sum + arr[i%n];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main(){
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"繰り返し連結後に作成された配列の最大部分配列合計は "<<calcMaxSubArraySum(arr, n, k);
    return 0;
}

出力

繰り返し連結後に作成された配列の最大部分配列合計は 26

まとめ

配列をk回連結した後の最大部分配列合計を求める問題では、以下の2つのアプローチがあります。

• シンプルな方法： 実際に連結後の配列を作成してからKadaneのアルゴリズムを適用する。理解しやすいが、メモリを余分に消費する。
• 剰余演算を使う方法： 配列を実際に作成せず、「i % n」でインデックスを参照する。メモリ効率が良く、実用的なおすすめの方法。

どちらの方法も計算量はO(k×n)ですが、剰余演算を使った方法は追加の配列を必要としないため、大規模なデータに対しても安全に動作します。ぜひ実際のコードで試してみてください。