C++で少なくともk個の要素を含む最大合計部分配列を求める方法

問題概要

長さ n の整数配列と正の整数 k が与えられたとき、「要素数が k 個以上の連続する部分配列」の中から合計が最大となるものを求めます。全探索では非効率ですが、カダネのアルゴリズムとスライディングウィンドウを組み合わせることで、O(n) の時間計算量でこの問題を効率的に解くことができます。

アルゴリズムの手順

プログラムの流れは以下の通りです。

• 配列を初期化します。
• サイズ n の max_sum 配列を用意し、max_sum[0] = a[0] とします。
• カダネのアルゴリズムを使い、「各インデックスで終わる部分配列の最大合計」をすべて求めて max_sum 配列に保存します。
• 最初の k 要素の合計を計算し、変数 sum に格納します。
• i = k から n-1 までループします。
  • sum に a[i] - a[i-k] を加算し、長さ k のウィンドウを右へスライドさせます。
  • result を max(result, sum) で更新します。
  • result を max(result, sum + max_sum[i-k]) で更新し、ウィンドウの左側に追加の部分配列をつなげた場合も考慮します。

C++での実装例

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
int getMaxSum(int a[], int n, int k) {
   int maxSum[n];
   maxSum[0] = a[0];
   int currentMax = a[0];
   // カダネのアルゴリズムで各位置で終わる最大合計を求める
   for (int i = 1; i < n; i++) {
      currentMax = max(a[i], currentMax+a[i]);
      maxSum[i] = currentMax;
   }
   // 最初のk個の合計を求める
   int sum = 0;
   for (int i = 0; i < k; i++) {
      sum += a[i];
   }
   int result = sum;
   // ウィンドウをスライドしながら最大値を更新
   for (int i = k; i < n; i++) {
      sum += a[i] - a[i-k];
      result = max(result, sum);
      result = max(result, sum + maxSum[i-k]);
   }
   return result;
}
int main() {
   int a[] = {5, 3, 7, -5, 6, 2, 1};
   int k = 6;
   cout << getMaxSum(a, 7, k) << endl;
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

19

アルゴリズムのポイント

このアルゴリズムの肝は、次の2つのテクニックを組み合わせている点です。

• スライディングウィンドウ: 長さがちょうど k の区間の合計を、要素を1つ追加して1つ削除するだけの O(1) 処理で更新しながら走査できます。
• maxSum[i-k] の活用: インデックス i-k で終わる最大部分配列の合計を加えることで、「k 個以上」という制約を満たしながら、k より長い部分配列も漏れなく考慮できます。

なお、int maxSum[n] は可変長配列(VLA)と呼ばれるもので、標準 C++ の仕様には含まれていません。移植性を重視する場合は、vector<int> maxSum(n) を使用することをおすすめします。

計算量は時間・空間ともに O(n) であり、大規模な入力に対しても高速に動作します。

まとめ

本記事では、C++において「少なくとも k 個の要素を含む最大合計部分配列」を O(n) で求める方法を解説しました。カダネのアルゴリズムとスライディングウィンドウの組み合わせは、他の部分配列関連の問題にも応用できる重要なテクニックです。ぜひマスターしておきましょう。本チュートリアルについてご不明な点がある場合は、コメント欄にてお気軽にお知らせください。