C++で合計がkより大きい最長部分配列を求める方法

このチュートリアルでは、C++を使って「合計（総和）が k より大きい最長の部分配列」を見つけるプログラムを作成します。単純な全探索では O(n²) の計算量が必要ですが、累積和と二分探索を組み合わせることで、O(n log n) まで効率化できます。負の数を含む配列にも対応できるのが特徴です。

解法のアルゴリズム

以下の手順で問題を解いていきます。

1. 配列を初期化します。
2. 配列を先頭から走査し、各インデックスにおける累積和とそのインデックスをペアとして vector に格納します。
3. 格納した累積和を、値とインデックスを基準にソートします。
4. 最小インデックスを保持するための配列を初期化します。
5. n 回繰り返すループを記述し、ソート済みの累積和配列を走査しながら、それまでに出現した最小のインデックスで値を更新していきます。
6. 合計を 0 に初期化し直します。
7. 再び n 回繰り返すループを記述します。
   • 現在の要素を合計に加算します。
   • 合計が k より大きい場合、最大部分配列の長さは i + 1 となります。
   • そうでない場合は、二分探索を使って過去の累積和からインデックスを探します。「sum − k − 1」以下となる最大の累積和が、求めたい要素のインデックスです。

実装例

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

// ペアを比較する関数（値を優先し、同値の場合はインデックス順）
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.first == b.first) {
        return a.second < b.second;
    }
    return a.first < b.first;
}

// val 以下の最大の累積和を持つ位置を二分探索で取得
int findIndex(vector<pair<int, int> >& previousSums, int n, int val) {
    int start = 0;
    int end = n - 1;
    int mid, result = -1;
    while (start <= end) {
        mid = (start + end) / 2;
        if (previousSums[mid].first <= val) {
            result = mid;
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return result;
}

int getLargestSubArray(int arr[], int n, int k) {
    int maxLength = 0;
    vector<pair<int, int> > previousSums;
    int sum = 0, minIndexes[n];

    // 各インデックスでの累積和を記録
    for (int i = 0; i < n; i++) {
        sum = sum + arr[i];
        previousSums.push_back({ sum, i });
    }

    // 累積和をソート
    sort(previousSums.begin(), previousSums.end(), compare);

    // 先頭からの最小インデックスを前処理で計算
    minIndexes[0] = previousSums[0].second;
    for (int i = 1; i < n; i++) {
        minIndexes[i] = min(minIndexes[i - 1], previousSums[i].second);
    }

    // 主処理：各区切り位置で最長の長さを更新
    sum = 0;
    for (int i = 0; i < n; i++) {
        sum = sum + arr[i];
        if (sum > k) {
            maxLength = i + 1;
        } else {
            int ind = findIndex(previousSums, n, sum - k - 1);
            if (ind != -1 && minIndexes[ind] < i) {
                maxLength = max(maxLength, i - minIndexes[ind]);
            }
        }
    }
    return maxLength;
}

int main() {
    int arr[] = { 5, 3, -3, 2, 4, 7 };
    int k = 5, n = 6;
    cout << getLargestSubArray(arr, n, k) << endl;
    return 0;
}

出力結果

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

6

この例では、配列全体 { 5, 3, -3, 2, 4, 7 } の合計が 18 となり、k = 5 を超えているため、条件を満たす最長の部分配列の長さは 6（配列全体）になります。

まとめ

本チュートリアルでは、累積和と二分探索を組み合わせることで、合計が k より大きい最長部分配列を O(n log n) の計算量で求める方法を紹介しました。負の数が含まれる配列でも正しく動作する点がポイントです。チュートリアルに関するご質問があれば、コメント欄でお気軽にお知らせください。