C++で部分配列を1回だけ反転して0の個数を最大化する方法

問題文

0と1のみから構成される2値配列（バイナリ配列）が与えられます。ここで、部分配列を1回だけ反転できるという条件のもとで、配列全体に含まれる0の個数を最大化することを考えます。

なお、反転操作とは、指定した範囲内のすべての0を1に、1を0に切り替える処理のことです。

具体例

次の配列を考えてみましょう。

arr = {1, 1, 0, 0, 0, 0, 0}

先頭の2つの「1」を「0」に反転すると、配列全体が次のようになります。

{0, 0, 0, 0, 0, 0, 0}

この場合、0の個数は7となり、これが最大値です。

解法のポイント

ある部分配列を反転すると、その範囲内の1は0に、0は1に変わります。したがって、反転後の0の総数は次の式で表せます。

最終的な0の個数 ＝ 元の配列の0の個数 ＋ （部分配列内の1の個数 − 部分配列内の0の個数）

つまり、「1の個数 − 0の個数」が最大となる部分配列を見つければよいことになります。

アルゴリズム

1. すべての部分配列を調べ、「1の個数 − 0の個数」の値が最大になる部分配列を探します。
2. この最大値を maxDiff とします。
3. 最終的な答えとして、元の配列の0の個数 ＋ maxDiff を返します。

この手法の計算量は、全ての開始位置・終了位置の組み合わせを調べるため O(n²) となります。

C++での実装例

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

int getMaxSubArray(int *arr, int n){
    int maxDiff = 0;
    int zeroCnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] == 0) {
            ++zeroCnt;
        }
        int cnt0 = 0;
        int cnt1 = 0;
        for (int j = i; j < n; ++j) {
            if (arr[j] == 1) {
                ++cnt1;
            }
            else {
                ++cnt0;
            }
            maxDiff = max(maxDiff, cnt1 - cnt0);
        }
    }
    return zeroCnt + maxDiff;
}

int main(){
    int arr[] = {1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum subarray size = " << getMaxSubArray(arr, n) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Maximum subarray size = 7

まとめ

本記事では、2値配列に対して部分配列を1回だけ反転できる場合に、0の個数を最大化する方法を紹介しました。鍵となるのは「反転によって増える0の数＝部分配列内の（1の個数 − 0の個数）」という着眼点です。全部分配列を走査するO(n²)のシンプルな実装で正しく解くことができます。