Max Consecutive Ones
Given a binary array nums
, return the maximum number of consecutive 1
's in the array.
Problem Statement
When you're given a problem like this, the first thing is to understand the problem statement and the constraints. In this case, we are given a binary array, where the elements are either 0 or 1, and we are asked to return the maximum number of consecutive 1's in the array.
Examples
Input: nums = [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.
Clarifying Questions
 Is the binary array a list of integers or boolean values?
 Are there any specific constraints on the size of the array, such as maximum length?
 Should I return the length of the maximum sequence or the sequence itself?
 Can the input array contain nonbinary values? If so, how should I handle them?
 Should I return 0 if there are no 1's in the array?
 Can the array have multiple sequences of the same maximum length, and should I return one of them or all of them?
 Is the input array guaranteed to be nonempty, or should I include special cases for an empty array?
 What is the expected input format for the binary array? Can it be assumed that it will always be a valid binary array with only 0's and 1's?
 Is the output required to be the length of the longest contiguous sequence of 1's or is it required to be the number of 1's in the longest contiguous sequence of 1's?
 Is there a requirement for the solution to have a specific time complexity or can any efficient solution be acceptable?
Solutions
There are several approaches to solving the problem of finding the maximum number of consecutive 1's in a binary array:
Here are the code implementations in various programming languages:
Approach I: Brute force
This involves using nested loops to check for consecutive 1's at each position in the binary array. This approach has a time complexity of O(n^2), where n is the length of the binary array.
Algorithm:
 Initialize a variable
maxCount
to 0, to keep track of the maximum number of consecutive 1's 
For each element
i
in the binary arraynums
: Initialize a variable
count
to 0 
For each element
j
starting fromi
until the end of the binary arraynums
:
If
nums[j]
is 1, incrementcount
 If
nums[j]
is 0, break out of the inner loop

If
 Set
maxCount
to the maximum ofmaxCount
andcount
 Initialize a variable
 Return
maxCount
Time Complexity: O(n^2), where n is the length of the input array. This is because for each element in the array, we are checking all of the elements that come after it.
Space Complexity: O(1), because we only use a few variables to keep track of the maximum count and the current count.
Approach II: Single pass
This approach involves keeping track of the count of consecutive 1's as we traverse the binary array in a single pass. This way, we can achieve a time complexity of O(n), where n is the length of the binary array.
Algorithm:

Initialize two variables
maxCount
to 0 andcount
to 0, to keep track of the maximum number of consecutive 1's and the current number of consecutive 1's, respectively 
For each element
i
in the binary arraynums
: If
nums[i]
is 1, incrementcount
 If
nums[i]
is 0, resetcount
to 0  Set
maxCount
to the maximum ofmaxCount
andcount
 If
 Return
maxCount
Time Complexity: O(n), where n is the length of the input array. This is because we are only looping through the array once.
Space Complexity: O(1), because we only use a few variables to keep track of the maximum count and the current count.
Approach III: Bit manipulation
This approach involves using bit manipulation techniques to count the number of consecutive 1's in the binary representation of the input. This can be an efficient solution for very large binary arrays but is less intuitive and harder to understand.
Algorithm:

Initialize two variables
maxCount
to 0 andcount
to 0, to keep track of the maximum number of consecutive 1's and the current number of consecutive 1's, respectively 
For each element
i
in the binary arraynums
: Convert
nums[i]
to its binary representation 
Use bit manipulation techniques to count the number of consecutive 1's in the binary representation of
nums[i]
 Set
count
to the maximum ofcount
and the number of consecutive 1's found in the binary representation  Set
maxCount
to the maximum ofmaxCount
andcount
 Convert
 Return
maxCount
Time Complexity: O(n), because we iterate through the array once, and the bitwise operations are constant time, so the time complexity is O(n).
Space Complexity: O(1), because we only need a constant amount of extra space to store the count and maxCount variables, so the space complexity is O(1).
Approach IV: Dynamic programming
This involves using dynamic programming techniques to keep track of the maximum number of consecutive 1's up to each position in the binary array. This approach has a time complexity of O(n), where n is the length of the binary array and is more memory efficient than the optimized single pass approach.
Algorithm:

Initialize an array
dp
of the same length as the binary arraynums
, to keep track of the maximum number of consecutive 1's up to each position 
For each element
i
in the binary arraynums
:
If
nums[i]
is 1, setdp[i]
todp[i1] + 1
 If
nums[i]
is 0, setdp[i]
to 0  Set
maxCount
to the maximum ofmaxCount
anddp[i]

If
 Return
maxCount
Time Complexity: O(n), where n is the length of the input array. This is because we are only looping through the array once.
Space Complexity: O(n), because we are using an array dp
of length n
to store the maximum consecutive
1's ending at each index.