Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

Input:
 [1,1,0,1,1,1]

Output:
 3

Explanation:
 The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

• The input array will only contain 0 and 1.

• The length of input array is a positive integer and will not exceed 10,000

Analysis

可以用两个指针寻找连续1的边界，i为第一个连续1的第一个index，j为连续1的最后一个index + 1

110111
^ ^
i = 0, j = 2

110111_
   ^  ^
i = 3, j = 6

另外一种思路 from @yuxiangmusic on LeetCode：

The idea is to reset maxHere to 0 if we see 0, otherwise increase maxHere by 1

The max of all maxHere is the solution

就是每次遇见了0就重新开始计数，不然增加当前记录的连续1的长度，比较所有的连续1长度就可以得到最大值。

比如：

110111
^ maxHere = 1

110111
.^ maxHere = 2

110111
..^ maxHere = 0

110111
...^ maxHere = 1

110111
....^ maxHere = 2

110111
.....^ maxHere = 3

Solution

Two Pointers - Two pointers for left and right boundaries each (8ms AC) - O(n) time, O(1) space

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int i = 0, j = 0;
        int max = 0;
        while (i < nums.length && j < nums.length) {
            while (i < nums.length && nums[i] != 1) {
                i++;
            }
            // i is the first index in the consecutive ones
            j = i;
            while (j < nums.length && nums[j] == 1) {
                j++;
            }
            // j is now the first non-one index on the right of the last consecutive ones
            max = Math.max(j - i, max);
            // search for next consecutive ones 
            i = j;
        }
        return max;
    }
}

Keeping track of length of current consecutive ones - O(n) time, O(1) space

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxHere = 0, max = 0;
        for (int n : nums)
            max = Math.max(max, maxHere = n == 0 ? 0 : maxHere + 1);
        return max; 
    } 
}

OR easier to read version @shawngao:

public class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int result = 0;
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
            count++;
            result = Math.max(count, result);
            }
            else count = 0;
        }

        return result;
    }
}

Reference

https://leetcode.com/problems/max-consecutive-ones/discuss/96693/Java-4-lines-concise-solution-with-explanation