【C++解説】0を1に置き換えて最長の連続する1の並びを実現する置換位置を見つける方法（Set-2）

概要

0と1から構成される配列が与えられたとき、その中の「0」を1つだけ「1」に置き換えることで、最も長い連続した1の並び（シーケンス）を実現できる置換位置を求める問題です。このアルゴリズムでは、時間計算量O(n)、補助空間O(1)という効率的な実装が求められます。

入力例と出力例

まず、具体的な例を見てみましょう。

入力：

arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}

出力：

Index 10

配列のインデックスは0から始まるとし、インデックス10にある0を1に置き換えると、最も長い連続する1の並びが得られます。

もう一つの例です。

入力：

arr[] = {1, 1, 1, 1, 1, 0}

出力：

Index 5

アルゴリズムの考え方：0の両側の1の数を数える

この問題の基本的な発想は、「各0について、その左右に存在する1の個数を数える」というものです。求めるべきインデックスとは、周囲に最大数の1を持つ0の位置ということになります。

このために、以下の変数を使用します。

• leftCnt … 現在注目している0の左側にある1の個数を保持します。
• rightCnt … 現在注目している0の右側にある1の個数を保持します。
• maxIndex … 周囲に最も多くの1を持つ0のインデックスを表します。
• lastInd … 最後に見つけた0のインデックスを表します。
• maxCnt … maxIndexの位置にある0を1に置き換えた場合に得られる1の総数を表します。

処理の手順

1. 配列の要素が1である間、rightCntを増加させ続けます。次の0がインデックスiに現れたと仮定します。
2. この0が最初の0要素かどうかを確認します。lastIndが有効なインデックス値を持っていない場合、それが最初の0要素とみなされます。
3. その場合、lastIndをiで更新します。この時点でのrightCntの値は、この0の左側にある1の個数を示しています。
4. 続いてleftCntをrightCntと等しくし、rightCntを再計算します。現在の0が最初の0でない場合、インデックスlastIndにある0の周囲の1の数は leftCnt + rightCnt で求められます。
5. この値（leftCnt + rightCnt + 1）が現在のmaxCntより大きければ、maxCntを更新し、maxIndex = lastInd とします。
6. 次に、インデックスiの0に対してrightCntが新しいleftCntとなり、lastIndがiに更新されます。再度rightCntを計算し、1の数をmaxCntと比較して、必要に応じてmaxCntとmaxIndexを更新します。
7. この手順を、配列内の後続の各0要素に対して繰り返します。
8. lastIndには、現在のleftCntとrightCntが計算対象となっている0のインデックスが格納されている点に注意してください。
9. 最終的に、1に置き換えるべき0のインデックスがmaxIndexに格納されます。

C++による実装例

// C++ program to find index of zero
// to be replaced by one to get longest
// continuous sequence of ones.
#include <bits/stdc++.h>
using namespace std;

// Used to returns index of 0 to be replaced
// with 1 to get longest continuous
// sequence of 1s. If there is no 0
// in array, then it returns -1.
int maxOnesIndex(bool arr1[], int n1){
    int i = 0;
    // Used to store count of ones on left
    // side of current element zero
    int leftCnt1 = 0;
    // Used to store count of ones on right
    // side of current element zero
    int rightCnt1 = 0;
    // Shows index of zero with maximum number
    // of ones around it.
    int maxIndex1 = -1;
    // Shows index of last zero element seen
    int lastInd1 = -1;
    // Shows count of ones if zero at index
    // maxInd1 is replaced by one.
    int maxCnt1 = 0;
    while (i < n1) {
        // Used to keep incrementing count until
        // current element is 1.
        if (arr1[i]) {
            rightCnt1++;
        }
        else {
            // It has been observed that if current zero element
            // is not first zero element,
            // then count number of ones
            // obtained by replacing zero at
            // index lastInd. Update maxCnt
            // and maxIndex if required.
            if (lastInd1 != -1) {
                if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
                    maxCnt1 = leftCnt1 + rightCnt1 + 1;
                    maxIndex1 = lastInd1;
                }
            }
            lastInd1 = i;
            leftCnt1 = rightCnt1;
            rightCnt1 = 0;
        }
        i++;
    }
    // Determine number of ones in continuous
    // sequence when last zero element is
    // replaced by one.
    if (lastInd1 != -1) {
        if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
            maxCnt1 = leftCnt1 + rightCnt1 + 1;
            maxIndex1 = lastInd1;
        }
    }
    return maxIndex1;
}

// Driver function
int main(){
    bool arr1[] = { 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1 };
    // bool arr1[] = {1, 1, 1, 1, 1, 0};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Index of 0 to be replaced is "
         << maxOnesIndex(arr1, n1);
    return 0;
}

実行結果

Index of 0 to be replaced is 10

まとめ

このアルゴリズムは、配列を一度走査するだけで答えが求められるため、時間計算量はO(n)です。また、使用する変数が固定個（leftCnt、rightCnt、maxIndex、lastInd、maxCnt）のみであるため、補助空間もO(1)に抑えられています。なお、配列内に0が一つも存在しない場合は、関数は-1を返すようになっています。スライディングウィンドウ的な発想で0をまたぐ1の連続数を管理することで、効率的に最適な置換位置を特定できる点が本手法のポイントです。