C++でバイナリ配列内の0を1に置き換えて最長の連続する1のシーケンスを取得する方法

N個の要素からなる配列を考えます。各要素は0または1のいずれかです。この中から1つの0を1に置き換えることで、最も長い連続した1のシーケンスを得られる位置を見つけるのが本記事のテーマです。

例えば、配列が arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] の場合、答えとなるインデックスは9です。インデックス9の0を1に置き換えることで、最大の連続する1のシーケンスが実現します。

アルゴリズムの考え方

この問題を効率的に解くには、次の3つのインデックスを追跡する必要があります。

• 現在のインデックス(curr)
• 直前の0のインデックス(pz)
• 前々回の0のインデックス(ppz)

配列を先頭から走査し、要素が0であるときに curr と ppz の差を計算します。この差が現在の最大値(count_max)より大きければ、最大値を更新します。走査が終わったら、最大の差に対応するpz(直前の0のインデックス)を返します。この手法により、時間計算量O(n)・空間計算量O(1)で問題を解くことができます。

サンプルコード

#include<iostream>
using namespace std;
int findIndex(bool arr[], int n) {
   int count_max = 0;
   int index;
   int pz = -1;
   int ppz = -1;
   for (int curr=0; curr<n; curr++) {
      if (arr[curr] == 0) {
         if (curr - ppz > count_max){
            count_max = curr - ppz;
            index = pz;
         }
         ppz = pz;
         pz = curr;
      }
   }
   if (n-ppz > count_max)
      index = pz;
   return index;
}
int main() {
   bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Index of 0 to be replaced is "<< findIndex(arr, n);
}

実行結果

Index of 0 to be replaced is 9

このコードでは、0が出現するたびに「前々回の0」と「現在の位置」の間隔を確認し、これまでの最大値と比較しています。こうすることで、任意の0を1に置き換えた場合に得られる最長の連続シーケンスを常に把握でき、最適な置き換え位置を特定できます。