Coder's Cat

2020-11-20

## 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 non-flipped.

Suppose we define two arrays:

`dp1[i]` stands for non-flipped 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[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!

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