public int findMaxConsecutiveOnes(int[] nums) {
int maxConsecutive = 0, zeroLeft = 0, zeroRight = 0;
for (int i=0;i<nums.length;i++) {
zeroRight++;
if (nums[i] == 0) {
zeroLeft = zeroRight;
zeroRight = 0;
}
maxConsecutive = Math.max(maxConsecutive, zeroLeft+zeroRight);
}
return maxConsecutive;
}
Java Concise O(n) Time O(1) Space


zero right can be considered as 1 accumulated. If the gap between 1 and 1 is only 1(zero), zeroleft can be a temp storage to store how many 1 has been calculated, and then move on accumulate. But if there are 2 or more 0 gap, after the 1st 0, left will only be used to the flipped single 1.


@compton_scatter How did you even think of this ? I just want to know your thought process. This is amazing :)

I came up with a different idea. Use variable index to record the position of zero, and initiate the index to 1. Once we find a zero, refresh the count and store the new index. But yours are very impressive. Never thought this way before!
public class Solution { public int findMaxConsecutiveOnes(int[] nums) { int max = 0, count = 0, index = 1; for(int i = 0;i< nums.length; i++){ if(nums[i] == 1){ count++; }else{ count = i  index; index = i; } max = Math.max(max,count); } return max; } }

Any 1/0 string with at least one trailing
0
can be seeing as repeating of a pattern:a
ones followed by 1 zero. We denote such a pattern byp(a)
. Eg:p(1) =def= 10 p(3) =def= 1110 p(5) =def= 111110 p(0) =def= 0
pay attention to the last one. Also note that, each occurrence of
0
signals the end of such a pattern.And such a string
0011011100
can be seen asp(0) + p(0) + p(2) + p(3) + p(0)
. Reminder, count a pattern at its trailing0
.In OP's solution, the two variables
zeroLeft
andzeroRight
serve these purposes: for each iteration, or indexi
zeroLeft
: the length of pattern that ends no later thani
.zeroRight
: the length of the run of1
ifi
is in one. 0 otherwise.
Here is a trace for your convenience :
0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 //entry 0 1 1 1 1 3 3 3 3 4 1 1 1 1 1 5 //zeroLeft 0 0 0 1 2 0 1 2 3 0 0 1 2 3 4 0 //zeroRight
So, at each
i
that is1
, we considerzeroLeft + zeroRight
because for an example like110111
, we are consideringlen(p(2)) + len(run(3))
(run(3)
as 3 consecutive1
s).The code's logic:
For each index i: if nums[i] is 0: calculate the length of the pattern that ends at nums[i] , and put it into zeroLeft. Reset zeroRight because we are no longer in a run; if nums[i] is 1: increment zeroRight which records run length, and try to update max with (zeroLeft + zeroRight);
Of course, OP wrote his code in another way, but I think that is the logic here. I solved this problem with a similar approach (considering the separating zeroes), but OP's code is way more elegant than mine.
Again, this is only my way of interpreting this program, and it's highly unlikely this is the thinking process of OP himself. The concept of a pattern is coined not necessarily. I do hope this will aid in the process of you finding your own way of interpretation.

Based on @compton_scatter 's brilliant solution.
Slight modification, instead of calculating Max value in each step, can just calculate when we hit a 0, and then finally one last time, before returning.
public int findMaxConsecutiveOnes(int[] nums) { int maxCons = 0; int zeroIncluded = 0; int count = 0; for (int i = 0; i < nums.length; i++) { count++; if (nums[i] == 0) { maxCons = Math.max(maxCons, zeroIncluded + count  1); zeroIncluded = count; count = 0; } } return Math.max(maxCons, zeroIncluded + count); }
Results in a slightly faster code.