C++で解く最大消去値（Maximum Erasure Value）― スライディングウィンドウによる効率的な実装

正の整数からなる配列が与えられたとき、すべての要素が一意（重複なし）である部分配列を1つだけ消去することを考えます。この操作で得られるスコアは、消去した部分配列の要素の総和です。

ここでの目的は、ちょうど1つの部分配列を消去したときに得られる最大の合計値を返すことです。

なお、配列 arr が a の部分配列であるとは、a[l], a[l+1], …, a[r] という形で表される連続した部分列と一致することを意味します。

入力例と出力例

例1

arr[ ] = { 1, 2, 4, 5, 6 }

出力：

17

説明： 最適な部分配列は {2, 4, 5, 6} です。その総和は 17 になります。

例2

arr[ ] = { 5, 3, 1, 3, 5, 3, 1, 3, 5 }

出力：

9

説明： 最適な部分配列は {5, 3, 1} または {1, 3, 5} です。いずれも総和は 9 になります。

この問題へのアプローチ

この問題はスライディングウィンドウ（Sliding Window）の概念を用いて解きます。このテクニックを使うと、二重ループを単一のループに変換でき、時間計算量を大幅に削減できます。

具体的には、左右2つのポインタ（left / right）とウィンドウの合計値 win を用意します。配列を先頭から走査しながら、現在のウィンドウ内の要素がすでにハッシュセット（HashSet）に存在するかどうかを判定します。

• すでに存在する場合 → 重複がなくなるまで左端の要素をセットから取り除き、ウィンドウを縮めます。
• 存在しない場合 → その要素をハッシュセットに追加し、ウィンドウの合計値に加算します。

各ステップで「これまでの結果」と「現在のウィンドウの合計値」を比較し、大きい方を結果として保持します。

アルゴリズムの手順

1. 正の整数からなる配列を入力として受け取ります。
2. 整数型関数 maximumUniqueSubarray(vector<int>& arr) が配列を受け取ります。
3. ポインタ i、j とウィンドウ合計 win を初期化し、配列を走査します。現在の要素がハッシュセットに存在すれば、重複が解消されるまで左端を除去してウィンドウを移動します。存在しなければ要素をセットに挿入し、win に加算します。
4. 結果 result と win の最大値を常に更新します。
5. 最終的な result を返します。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
int maximumUniqueSubarray(vector<int>& arr) {
    int result = 0;
    unordered_set<int> hashset;
    for (int i = 0, j = 0, win = 0; j < arr.size(); j++) {
        while (hashset.find(arr[j]) != hashset.end()) {
            hashset.erase(arr[i]);
            win -= arr[i];
            i++;
        }
        hashset.insert(arr[j]);
        win += arr[j];
        result = max(result, win);
    }
    return result;
}
int main(){
    vector<int>nums;
    nums<<5,3,1,3,5,3,1,3,5;
    cout<<maximumUniqueSubarray(nums)<<endl;
    return 0;
}

実行結果

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

9

この実装では、各要素が高々1回ずつ追加・削除されるため、時間計算量は O(n)、ハッシュセットに必要な空間計算量も O(n) となり、非常に効率的に最大消去値を求めることができます。