This post is completed by 5 users

  • 0
 Add to List
Beginner

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)

 



import java.util.Arrays;

public class Main {

    public static void findMaxConsecutiveOnes(int[] input) {
        int ones = 0;
        int max = 0;
        for(int i=0; i<input.length; i++){
            if(input[i]==1)
                ones++;
            else{
                max = Math.max(ones, max);
                ones = 0;
            }
        }
        max = Math.max(ones, max);
        System.out.println("Input: " + Arrays.toString(input) + ", Max consecutive ones: " + max);
    }

    public static void main(String[] args) {
        int [] input = {0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1};
        findMaxConsecutiveOnes(input);
    }
}



import numpy as np

class MaximumConsecutiveOnes:
    def findMaxConsecutiveOnes(self, input):
        ones = 0
        max_ones = 0
        for num in input:
            if num == 1:
                ones += 1
            else:
                max_ones = max(ones, max_ones)
                ones = 0
        max_ones = max(ones, max_ones)
        print(f"Input: {input}, Max consecutive ones: {max_ones}")

if __name__ == "__main__":
    input = [0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1]
    MaximumConsecutiveOnes().findMaxConsecutiveOnes(input)



package main

import (
	"fmt"
)

type MaximumConsecutiveOnes struct{}

func (mco *MaximumConsecutiveOnes) findMaxConsecutiveOnes(input []int) {
	ones := 0
	maxOnes := 0
	for _, num := range input {
		if num == 1 {
			ones++
		} else {
			maxOnes = max(ones, maxOnes)
			ones = 0
		}
	}
	maxOnes = max(ones, maxOnes)
	fmt.Printf("Input: %v, Max consecutive ones: %d", input, maxOnes)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	input := []int{0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1}
	maxConsecutiveOnes := MaximumConsecutiveOnes{}
	maxConsecutiveOnes.findMaxConsecutiveOnes(input)
}

Output:

Input: [0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1], Max consecutive ones: 4

Related Problems: