|
This post is completed by 5 users
|
Add to List |
530. Find Maximum Consecutive Ones in an Array
Given a binary array (contains only 0's and 1's), find out the number of maximum consecutive ones.
Example:
Input: [0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1] Max consecutive ones: 4 Input: [0, 1, 1, 0, 1, 1], Max consecutive ones: 2 Input: [0, 0, 0, 0] Max consecutive ones: 0
Solution:
Initialize max = 0, currentOnes = 0.Now iterate the given input array and if the current element is 1 then do currentOnes++. If the current element is 0 then check if max<currentOnes, if yes then do max = currentOnes and reset currentOnes=0. Once the iteration is over, handle the special case when the last element is 1, again check currentOnes with max and update max if necessary.
Time Complexity: O(N)
Output:
Input: [0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1], Max consecutive ones: 4