#LeetCode: Maximum consecutive one's

Also Check: LeetCode Solutions in Java

Let's say we want to find maximum consecutive one’s in a binary array.

Algorithm:
1). Maintain two counters current and max.
2). Start iterating the array, if 3.a). the current number is 1, we need to increment 'current'.
3). If the current number is 0, then we need perfom below checks:
3.a) If the 'current' is greater than 'max', we set 'current' in 'max'.
3.b). If max is greater than equal to half of array length, so we should return max as there is no point in checking the array further.
3.c). Set the 'current' as zero.
4). Return 'current' or 'max', which ever is higher.

GIT URL: Java Solution of Maximum consecutive one's problem



What will happen if the binary array is circular?
Algorithm:
1). We will start iterating the array from left to right till we encounter a zero, during the iteration we will increment 'onesFromStart'. And 'start' will contain the index where we last constinous one was present.
2). We will start iterating the array from right to left till we encounter a zero, during the iteration we will increment 'onesFromEnd'. And 'end' will contain the index where we last constinous one was present
3). When onesFromStart is greater than onesFromEnd, that means array contain all 1's.
4). We will maintain 2 count 'result' and 'onesInMid'. We will start iterating the array from 'start' to 'end' (i.e mid region). We will increment onesInMid when we get 1, else we will set onesInMid as 0 when we encounter zero.
5). At the end the max(result, onesFromStart + onesFromEnd) will give the maximum number of constinous 1s. Here onesFromStart + onesFromEnd is the number of constinous one when we when we join end and start of the array.



-K Himaanshu Shuklaa..