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 0and1
• The length of input array is a positive integer and will not exceed 10,000

Brainstorm

This is one of the more straightforward problems that I have done so far. We can simply iterate over the array and count the number of 1's while maintaining a max variable to keep track of the greatest number of consecutive 1's.

Approach #1: Iterate Array, Maintain Curr and Max Variables

We simply compare the adjacent elements and if they are both 1's, increment the variable that indicates the current number of 1's counted. When we encounter a 0 next to a 1, we break and replace the max variable with the current one, if the current is greater. At the end, we must do a final comparison between max and current (because at this time we've broken out of the loop and it is possible the last string of consecutive 1's is the longest).

int findMaxConsecutiveOnes(vector<int>& nums) {
    int max = 0, curr = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 1) 
            curr++;
        else {
            if (curr > max) max = curr;
            curr = 0;   
        }
    }
    return (max > curr) ? max : curr;
}

Time complexity: $$O(n)$$

Iterating through the array will be O(n), and each operation performed within the loop is constant time.

Space complexity: $$O(1)$$