Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Max Consecutive Ones

Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

The array contains only 0s and 1s. Print the length of the longest run of consecutive 1s.

Input

First line: n. Second line: n space-separated integers.

Output

The longest run of 1s.

Constraints

Example 1

Input

6
1 1 0 1 1 1

Output

3

Example 2

Input

2
0 0

Output

0

Hints

  1. Keep a counter for the current run of 1s.
  2. A 0 resets the counter; after every 1, update the best answer.

Approach

Scan once. On a 1, increase run and update best = max(best, run). On a 0, reset run to 0.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x, run = 0, best = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        run = (x == 1) ? run + 1 : 0;
        best = max(best, run);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = sys.stdin.read().split()
n = int(data[0])
run = best = 0
for x in data[1 : n + 1]:
    run = run + 1 if x == "1" else 0
    best = max(best, run)
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), run = 0, best = 0;
        for (int i = 0; i < n; i++) {
            run = sc.nextInt() == 1 ? run + 1 : 0;
            best = Math.max(best, run);
        }
        System.out.println(best);
    }
}

Solve Max Consecutive Ones online · All practice problems