【C++】他の配列の同じウィンドウの要素が一意になるときの、配列ウィンドウの最大合計の求め方

はじめに

本記事では、ある配列内のウィンドウ(連続する部分範囲)の合計値が最大となり、かつ同じ位置のウィンドウに対応する別の配列の要素がすべて一意(重複なし)である場合の、その最大合計を求めるプログラムについて解説します。

具体的には、要素数が等しい2つの配列 A と B が与えられます。目的は、配列 A の対応するウィンドウ内の要素がすべて重複なく一意であるという条件を満たす中で、配列 B のウィンドウの合計が最大になる範囲を見つけることです。

アルゴリズムの考え方(スライディングウィンドウ)

この問題は「スライディングウィンドウ(尺取り法)」とハッシュセット(unordered_set)を組み合わせることで、O(n) の時間計算量で効率的に解くことができます。手順は以下の通りです。

1. 左端 curr_begin と右端 i で表されるウィンドウを管理します。
2. 右端を1つずつ進めながら、配列 A の要素を unordered_set に登録していきます。
3. A[i] がすでにセットに存在する場合、重複が解消されるまで左端の要素をセットから削除し、合計値からも差し引いてウィンドウを縮めます。
4. 各ステップで現在のウィンドウの合計 curr_sum を更新し、これまでの最大値 result と比較して大きい方を保持します。

C++による実装例

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

// 最大合計を持つウィンドウの合計値を返す関数
int returnMaxSum(int A[], int B[], int n) {
    // 要素を管理するためのセット
    unordered_set<int> mp;
    int result = 0;
    int curr_sum = 0, curr_begin = 0;
    for (int i = 0; i < n; ++i) {
        // 重複がなくなるまでウィンドウの左側を縮める
        while (mp.find(A[i]) != mp.end()) {
            mp.erase(A[curr_begin]);
            curr_sum -= B[curr_begin];
            curr_begin++;
        }
        mp.insert(A[i]);
        curr_sum += B[i];
        result = max(result, curr_sum);
    }
    return result;
}

int main() {
    int A[] = { 0, 1, 2, 3, 0, 1, 4 };
    int B[] = { 9, 8, 1, 2, 3, 4, 5 };
    int n = sizeof(A)/sizeof(A[0]);
    cout << returnMaxSum(A, B, n);
    return 0;
}

出力

20

出力の解説

この例では、インデックス 0〜3 のウィンドウに注目すると、対応する配列 A の要素は {0, 1, 2, 3} となり、すべて一意です。このとき配列 B の合計は 9 + 8 + 1 + 2 = 20 となります。他のどの一意なウィンドウ(例：インデックス 2〜6 の合計 15)よりも合計が大きいため、答えは 20 になります。

計算量

• 時間計算量: O(n) — 各要素の挿入・削除はそれぞれ最大1回ずつしか行われないためです。
• 空間計算量: O(n) — セットに格納される要素数に依存します。