C++ STLのsetを使ってサイズkのすべての部分配列の最大値を効率的に求める方法

このチュートリアルでは、C++ STLのset（std::set）を活用して、サイズkのすべての部分配列（サブアレイ）から最大値を取り出し、その合計を求めるプログラムについて解説します。

長さNの整数型配列と整数Kが与えられたとき、先頭からK個ずつ範囲をずらしながら（スライディングウィンドウ方式）、それぞれの範囲内での最大値を求め、それらをすべて合計して出力するのが今回の課題です。

アルゴリズムのポイント

この問題を効率的に解く鍵となるのが、C++ STLのset<pair<int, int>>です。

• pair構造の活用： 要素の「値」と「インデックス」をペアで格納することで、同じ値が複数存在しても正しく区別できます。
• 自動ソート： setは常に昇順で要素を保持するため、rbegin()（逆イテレータ）を使えば即座に最大値へアクセスできます。
• 高速な挿入・削除： ウィンドウが移動するたびに、左端の要素を削除して右端に新しい要素を追加するだけで済みます。

挿入・削除・最大値の取得はそれぞれO(log K)で行えるため、全体の計算量はO(N log K)。毎回ウィンドウ内を走査する素朴な手法（O(N×K)）と比べて大幅に高速です。

サンプルコード

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

// 各部分配列の最大値の合計を返す関数
int maxOfSubarrays(int arr[], int n, int k){
    set<pair<int, int> > q;
    set<pair<int, int> >::reverse_iterator it;

    // 最初のk個の要素をsetに挿入
    for (int i = 0; i < k; i++) {
        q.insert(pair<int, int>(arr[i], i));
    }

    int sum = 0;
    // スライディングウィンドウで各最大値を加算
    for (int j = 0; j < n - k + 1; j++) {
        it = q.rbegin();
        sum += it->first;   // 現在のウィンドウの最大値を加算
        if (j + k < n) {    // 配列の範囲外アクセスを防止
            q.erase(pair<int, int>(arr[j], j));          // 左端の要素を削除
            q.insert(pair<int, int>(arr[j + k], j + k)); // 右側に新しい要素を挿入
        }
    }
    return sum;
}

int main(){
    int arr[] = { 4, 10, 54, 11, 8, 7, 9 };
    int K = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxOfSubarrays(arr, n, K);
    return 0;
}

実行結果

182

処理の流れを確認

上記の例（配列 {4, 10, 54, 11, 8, 7, 9}、K=3）では、次のように各ウィンドウの最大値が求められます。

• {4, 10, 54} → 最大値 54
• {10, 54, 11} → 最大値 54
• {54, 11, 8} → 最大値 54
• {11, 8, 7} → 最大値 11
• {8, 7, 9} → 最大値 9

これらを合計すると 54 + 54 + 54 + 11 + 9 = 182 となり、プログラムの出力と一致します。最後のウィンドウでは要素の入れ替えが不要になるため、コードでは範囲チェックを入れて安全性を高めています。