# Find maximum length sequence of continuous ones

Given a binary array, find the index of 0 to be replaced with 1 to get maximum length sequence of continuous ones.

For example,

Consider the array { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 }.
The index to be replaced is 7 to get continuous sequence of length 6 containing all 1’s.

The idea is very simple. We update each non-zero elements of array with count of their adjacent consecutive 1’s. For example, array { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 } is converted to { 0, 0, 1, 0, 3, 3, 3, 0, 2, 2 }. Now the problem reduces to finding the index of 0 whose sum of left and right element is maximum.

Below is C and Java implementation of the same. Note that this approach will modify the array and at-least requires two traversals of the array. We can use an auxiliary array to avoid modification of original array or restore the original array before returning.

## Java

Output:

Index to be replaced is 7

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

We have discussed two more approaches to solve this problem (here and here).

(1 votes, average: 5.00 out of 5)