# 487. Max Consecutive Ones II 最大连续1的个数 II

@TOC

## # 题目描述

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

Example 1:

``````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:

1. The input array will only contain 0 and 1.
2. 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?

## # 解题方法

### # 动态规划

1. left的含义是：遇到了0，并翻转了该0时，包含该0的位置和其左侧连续的1的的长度。
2. right的含义是：从上次遇到0之后，累加得到的连续1的个数。

10110
left startleft endright startright end, `i`

1. 当遇到1时，用right保存已经遇到的连续的1（不含翻转0得到的1）。
2. 当遇到0时，把这个0翻转，更新left为right + 1（把位置的0翻转为1），更新right为0。

`left+right`的最大值即为所求。

C++代码如下：

``````class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
const int N = nums.size();
if (N == 0) return 0;
int left = 0, right = 0;
int res = 0;
for (int i = 0; i < N; ++i) {
if (nums[i] == 1) {
right++;
} else {
left = right + 1;
right = 0;
}
res = max(res, left + right);
}
return res;
}
};
``````

## # 日期

2019 年 9 月 21 日 —— 莫生气，我若气病谁如意