C++でサイズkの部分配列の最大（最小）合計を効率的に求める方法

この記事では、配列 arr[] と整数 k が与えられたときに、サイズ k の部分配列（連続する要素）の合計の最大値（または最小値）を求める問題を解説します。

問題の例

入力：arr[] = {55, 43, 12, 76, 89, 25, 99}、k = 2

出力：165

説明：

サイズ2の部分配列の中では、{76, 89} の合計である 76 + 89 = 165 が最大となります。

解法アプローチ

1. 全探索（単純なアプローチ）

最も単純な方法は、サイズ k のすべての部分配列を列挙し、それぞれの合計を計算して最大値を返すことです。ただし、この方法の計算量は O(n×k) となるため、配列が大きい場合には非効率です。

2. スライディングウィンドウ法（効率的なアプローチ）

より効率的なのがスライディングウィンドウを使う方法です。まず最初の k 個の要素の合計を計算し、その後ウィンドウを1つずつ右にずらしながら、「直前のウィンドウの先頭要素を引き、新しく入ってくる要素を足す」という操作を繰り返します。これにより、各ステップの合計を O(1) で更新でき、全体の計算量は O(n) に抑えられます。

最後に、得られた部分配列の合計の中から最大値を返します。

実装プログラム

以下は、スライディングウィンドウ法を用いたC++の実装例です。

#include <iostream>
using namespace std;

int findMaxSumSubarray(int arr[], int n, int k) {

    if (n < k) {
        cout << "Invalid";
        return -1;
    }

    // 最初のk個の要素の合計を計算
    int maxSum = 0;
    for (int i = 0; i < k; i++)
        maxSum += arr[i];

    // ウィンドウをスライドさせながら最大値を更新
    int curr_sum = maxSum;
    for (int i = k; i < n; i++) {
        curr_sum += arr[i] - arr[i-k];
        maxSum = max(maxSum, curr_sum);
    }
    return maxSum;
}

int main() {

    int arr[] = {55, 43, 12, 76, 89, 25, 99};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    cout << "サイズ " << k << " の部分配列の最大合計は " << findMaxSumSubarray(arr, n, k);
    return 0;
}

出力

サイズ 2 の部分配列の最大合計は 165

まとめ

サイズ k の部分配列の最大合計を求める問題は、スライディングウィンドウ法を使うことで O(n) の時間計算量で効率的に解けます。同様の手法は「最小合計」を求める場合にも応用でき、max を min に置き換えるだけで簡単に対応できます。