C++で指定された合計以下となる最大合計の部分配列を求める方法

問題の概要

この問題では、整数の配列と合計値（上限）が与えられます。求めるのは、「要素の合計が指定された値以下となる部分配列（連続する要素の並び）」のうち、合計が最大になるものです。

配列の長さを n とするとき、長さが n 以下の任意の部分配列を対象に、合計が指定値を超えない範囲で最大の合計を見つけなければなりません。

入力と出力の例

入力： array = {3, 5, 1, 8, 2, 9}, sum = 25

出力： 25

解説： 合計が25以下となる部分配列のうち最大なのは {5, 1, 8, 2, 9} で、その合計はちょうど25です。配列全体の合計は28なので上限を超え、これが最適解となります。

単純なアプローチとその課題

最も直感的な方法は、配列を二重ループで走査してすべての部分配列の合計を計算し、指定値以下のものの中から最大を探すことです。しかし、この方法では2つのループが必要なため、時間計算量は O(n²) となり、配列が大きくなると処理が非常に遅くなります。

効率的な解法：スライディングウィンドウ法

より効率的なのが「スライディングウィンドウ（滑動窓）」を使う方法です。現在のウィンドウ内の合計と最大合計を常に比較しながら、条件に応じてウィンドウへ要素を追加したり、左端から要素を取り除いたりすることで答えを絞り込んでいきます。

具体的な流れは次のとおりです。

1. ウィンドウの左端 start と現在の合計 sum を初期化します。
2. 配列を先頭から順に走査し、新しい要素を加えても合計が上限を超えない場合はウィンドウを拡張します。
3. 合計が上限を超える場合は、超えなくなるまで左端の要素を取り除きます。
4. 各時点で合計が上限以下であれば、全体の最大値 overallMax を更新します。

この方法なら配列を一度だけ走査すればよく、時間計算量は O(n)、追加メモリは O(1) で済みます。ただし、この手法が正しく機能するのは配列の要素がすべて0以上の場合である点に注意してください。負の値が含まれる場合は、累積和とソートを組み合わせるなどの別のアルゴリズムが必要になります。

C++での実装例

上記の考え方を実装したプログラムがこちらです。

#include <iostream>
using namespace std;
int findMax(int a, int b){
    if(a>b)
        return a;
    return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
    int sum = arr[0], overallMax = 0, start = 0;
    for (int i = 1; i < n; i++) {
        if (sum <= maxSum)
        overallMax = findMax(overallMax, sum);
        while (sum + arr[i] > maxSum && start < i) {
            sum -= arr[start];
            start++;
        }
        sum += arr[i];
    }
    if (sum <= maxSum)
        overallMax = findMax(overallMax, sum);
    return overallMax;
}
int main(){
    int arr[] = {3, 1, 4, 7, 2, 9, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 20;
    cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
    return 0;
}

実行結果

The maximum sum of subarray with sum less than or equal to 20 is 18

この例では、配列 {3, 1, 4, 7, 2, 9, 5} の中から合計が20以下となる最大の部分配列が見つかり、その合計は18です。該当するのは {7, 2, 9} で、7 + 2 + 9 = 18 となります。

まとめ

指定された合計以下となる最大合計の部分配列を求める問題は、スライディングウィンドウ法を使うことで O(n²) の全探索から O(n) の線形時間へと大幅に高速化できます。要素が非負であることを前提に、ウィンドウの伸縮を制御するこのパターンは、「最大合計」「最小長」「指定範囲内の合計」など、さまざまな配列操作の問題に応用できる重要なテクニックです。