C++で解くMax Consecutive Ones II:0を1回反転できる場合の最大連続1数の求め方

0と1のみから構成されるバイナリ配列が与えられたとき、「0を最大1回だけ反転できる」という条件下で、配列内に存在する連続した1の最大個数を求める問題について解説します。

例えば、入力が [1,0,1,1,0] の場合、出力は 4 となります。最初に出現する0を反転すれば [1,1,1,1,0] となり、先頭から4つ連続した1が得られるためです。

解法の考え方:スライディングウィンドウ

この問題は、スライディングウィンドウ(尺取り法)を用いることで、線形時間で効率的に解くことができます。ウィンドウ内に含まれる0の個数が「1個以内」に収まるように、右端を伸ばしながら左端を調整していくのがポイントです。

具体的な手順は以下の通りです。

• 答えとなる変数 ret を 1、配列サイズ n を nums の要素数として初期化します。
• n が 0(空配列)の場合は、そのまま 0 を返します。
• ウィンドウ左端 j を 0、ウィンドウ内の0の個数を数える zero を 0 として初期化します。
• i を 0 から n-1 まで動かしながら、以下を繰り返します。
  • nums[i] が 0 なら、zero を 1 増やします。
  • zero が 1 を超えている間(j ≤ i の間)、ウィンドウ左端を縮めます。nums[j] が 0 なら zero を 1 減らし、j を進めます。
  • ret と現在のウィンドウ幅 (i − j + 1) を比較し、大きい方で ret を更新します。
• 最後に ret を返します。

C++での実装例

それでは、上記の手順を実際のC++コードで確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findMaxConsecutiveOnes(vector<int>& nums) {
      int ret = 1;
      int n = nums.size();
      if (!n)
         return 0;
      int j = 0;
      int zero = 0;
      for (int i = 0; i < n; i++) {
         if (nums[i] == 0) {
            zero++;
         }
         while (j <= i && zero > 1) {
            if (nums[j] == 0) {
               zero--;
            }
            j++;
         }
         ret = max(ret, i - j + 1);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,1,1,1,0,1,1};
   cout << (ob.findMaxConsecutiveOnes(v));
}

実行結果

入力:

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

出力:

6

計算量について

このアルゴリズムでは、配列の各要素が走査されるのは高々2回ずつ(右端 i の拡張時と左端 j の縮小時)であるため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。入力 {1,0,1,1,1,0,1,1} の場合、後半の0を反転することで6個の連続した1が得られるため、正しく 6 が出力されます。