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

Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 4.
Solution of dynamic programming
This problem is the variant of previous Max Consecutive Ones, only with one more limitation that we can flip one 1 to 0.
We can still use the dynamic programming method to solve it, but we need to distinguish the two states, flipped or nonflipped.
Suppose we define two arrays:
dp1[i]
stands for nonflipped state, the max consecutive length end at position i
.
dp2[i]
stands for flipped state, the max consecutive length end at position i
.
The trivial difference in the recurrence relation is we can not add one based on dp2[i1]
, since we can only flip one 1 to 0.
But we can use dp1[i1]+1
, since we haven’t flipped ones in this state.

An simpler solution
This problem is a special case of Max Consecutive Ones III. We can use the twopointer approach to solve it.

Join my Email List for more insights, It's Free!😋