[LintCode] Problem 883 - Max Consecutive Ones II

Posted on | In ,

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

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.

Example

No.1

Input: nums = [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.

No.2

Input: nums = [1,0,1,0,1]

Output: 3

Explanation:
Flip each zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 3.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int findMaxConsecutiveOnes(int[] nums) {
    int max = 0;
    int start = 0;
    int end = 0;
    int zero = 0;

    while (end < nums.length) {
        if (nums[end] == 0)
            zero++;

        while (zero > 1) {
            if (nums[start] == 0)
                zero--;
                
            start++;
        }

        max = Math.max(max, end - start + 1);
        end++;
    }

    return max;
}