# 487. Max Consecutive Ones II

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

**Example 1:**<br>

```
Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
    After flipping, the maximum number of consecutive 1s is 4.
```

**Note:**

* The input array will only contain `0` and `1`.
* The length of input array is a positive integer and will not exceed 10,000

**Follow up:**\
What if the input numbers come in one by one as an **infinite stream**? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?

```cpp
// Sliding window
int findMaxConsecutiveOnes(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0, zero_cnt = 0, begin = 0, end = 0;
    while (end < nums.size()) {
        if (nums[end++] == 0) ++zero_cnt;
        while (zero_cnt > 1) {
            if (nums[begin++] == 0) --zero_cnt;
        }
        res = max(res, end - begin);
    }
    return res;
}
```

```cpp
// Follow-Up: Sliding window
int findMaxConsecutiveOnes(vector<int>& nums) { // time: O(n); space: O(k)
    int res = 0, k = 1, begin = 0, end = 0;
    queue<int> zero_idx;
    while (end < nums.size()) {
        if (nums[end] == 0) zero_idx.push(end);
        ++end;
        while (zero_idx.size() > k) {
            begin = zero_idx.front() + 1;
            zero_idx.pop();
        }
        res = max(res, end - begin);
    }
    return res;
}
```

```cpp
// Follow-Up: Sliding window with k = 1
int findMaxConsecutiveOnes(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0, q = -1, begin = 0, end = 0;
    while (end < nums.size()) {
        if (nums[end] == 0) {
            begin = q + 1;
            q = end;
        }
        ++end;
        res = max(res, end - begin);
    }
    return res;
}
```
