Pythonで「最大消去値」を求めるプログラム ― スライディングウィンドウ法による解説

問題の概要

正の整数のみを含む配列 nums が与えられます。この中から要素がすべて一意（重複なし）である部分配列をちょうど1つ選んで「消去」し、その部分配列に含まれる要素の合計値をスコアとして得ます。求めたいのは、この操作で取得できるスコアの最大値です。

例えば、入力が nums = [6,3,2,3,6,3,2,3,6] の場合、出力は 11 になります。これは、最適な部分配列が [6,3,2] または [2,3,6] のいずれかであり、どちらも合計が 11 になるためです。

解き方のアプローチ：スライディングウィンドウ

この問題はスライディングウィンドウ（尺取り法）を使うことで効率的に解けます。左端 l と右端 r の2つのポインタを管理し、ウィンドウ内の要素が常に重複しない状態を保ちます。

用意する変数は次のとおりです。

• seen：各要素の値と、それが最後に出現したインデックスを記録する辞書（マップ）
• ans：現時点での最大スコア（初期値 0）
• sum：現在のウィンドウ内の要素の合計（初期値 0）
• l：ウィンドウの左端インデックス（初期値 0）

配列の各インデックス r とその値 x に対して、以下の手順で処理を進めます。

• x がすでに seen に存在する場合は、重複を解消する必要があります。前回の出現位置 index = seen[x] を取得し、l <= index の間、ウィンドウ左端の要素を取り除いていきます（seen から削除し、sum からも減算、その後 l を1つ進める）。
• seen[x] = r として現在位置を記録します。
• sum += x で現在の要素を合計に加算します。
• ans を ans と sum の大きい方の値で更新します。

ループが終わったら ans を返せば、それが答えになります。

Pythonでの実装例

実際のコードは次のようになります。

def solve(nums):
    seen = dict()
    ans = sum = 0
    l = 0
    for r, x in enumerate(nums):
        if x in seen:
            index = seen[x]
            while l <= index:
                del seen[nums[l]]
                sum -= nums[l]
                l += 1

        seen[x] = r
        sum += x
        ans = max(ans, sum)
    return ans

nums = [6,3,2,3,6,3,2,3,6]
print(solve(nums))

実行結果

入力：

[6,3,2,3,6,3,2,3,6]

出力：

11

計算量について

このアルゴリズムでは、各要素はウィンドウへの追加・削除ともに高々1回しか行われません。そのため、時間計算量は O(n)、要素の出現位置を記録する辞書 seen の分だけ空間計算量も O(n) となり、大きな入力に対しても高速に動作します。