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 non-flipped.
Suppose we define two arrays:
dp1[i] stands for non-flipped state, the max consecutive length end at position
dp2[i] stands for flipped state, the max consecutive length end at position
The trivial difference in the recurrence relation is we can not add one based on
dp2[i-1], since we can only flip one 1 to 0.
But we can use
dp1[i-1]+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 two-pointer approach to solve it.
Preparing for an interview? Check out this!