C++で解く「Max Consecutive Ones III」：スライディングウィンドウで最長の1の連続を求める

0と1のみから構成される配列Aが与えられ、そのうち最大K個の値を0から1へ更新できるものとします。このとき、1のみを含む最も長い（連続した）部分配列の長さを求めるのがこの問題です。

例として、A = [1,1,1,0,0,0,1,1,1,1,0]、k = 2 の場合を考えてみましょう。2つの0を1に反転すると、配列は [1,1,1,0,0,1,1,1,1,1,1] のようになり、連続する1の最長列の長さは 6 になります。

解き方：スライディングウィンドウ法

この問題はスライディングウィンドウ（2ポインタ）を使うことで、線形時間 O(n) で効率的に解けます。ウィンドウ内に含まれる0の個数が常にK以下になるよう制御しながら右端を拡張し、各時点でのウィンドウ幅の最大値を記録していくのが基本的な考え方です。

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

• ans := 0、j := 0、n := 配列のサイズ と初期化する
• i を 0 から n − 1 まで順に処理する
  • A[i] が 0 なら、k を 1 減らす
  • j <= i かつ k < 0 の間、次を繰り返す
    • A[j] が 0 なら、k を 1 増やす
    • j を 1 増やす
  • ans := max(i − j + 1, ans) で答えを更新する
• 最後に ans を返す

ここで、i はウィンドウの右端、j は左端を表します。k が負になった（＝反転できる0の数を超えてしまった）時点で、左端 j を0を通過するまで進めることで、ウィンドウ内の0の個数を再び K 以下に戻しています。

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

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

入力

[1,1,1,0,0,0,1,1,1,1,0]
3

出力

10

この実行例では k = 3 を指定しているため、3つの0（インデックス3〜5）を反転でき、結果として長さ10の区間が最長となります。冒頭の例のように k = 2 の場合は、反転できる0が2個だけなので、最長は6になります。

計算量

• 時間計算量：O(n) — 左端・右端の各ポインタは配列全体で最大1回ずつしか進まないためです。
• 空間計算量：O(1) — 追加のデータ構造は一切不要です。