Leetcode.485&487&1004 Max Consecutive One

Max Consecutive One serials

Find the longest consective subarray
Time: O(n) Space: O(1) max and cur_max

*Leetcode.485 findMaxConsecutiveOnes

1
2
3
4
5
6
7
public int findMaxConsecutiveOnes(int[] nums){
	int max, cur_max;
	for(int i = 0; i < nums.length; i++){
		max = Math.max(max, cur_max= nums[i]==0?0:cur_max+1);
	}
	return max;
}

Leetcode.487 findMaxConsecutiveOnesII

  • condition: if you can flip at most one 0.
  • Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?
1
2
3
4
5
6
7
8
9
10
11
12
13
public int findMaxConsecutiveOnesII(){
	int max = 0, zero = 0;
	for(int l = 0, h = 0; h < nums.length; h++){
		if(nums[h] == 0) zero++;
		while(zero > 1){
			if(nums[l++]==0){
				zero--;
			}
		}
		max = Math.max(max, h-l+1);
	}
	return max;
}

Leetcode.1004 findMaxConsecutiveOnesIII

  • condition: if you can flip at most k times.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public int findMaxConsecutiveOnes(int[] nums) {
            int max = 0, zero = 0, k = 1; // flip at most k zero
            for (int l = 0, h = 0; h < nums.length; h++) {
                if (nums[h] == 0)                                           
                    zero++;
                while (zero > k)
                    if (nums[l++] == 0)
                        zero--;                                     
                max = Math.max(max, h - l + 1);
            }                                                               
            return max;             
        }