Getting everything ready for you…

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

0s

Practice › Arrays

Practice Streak

Easy · Arrays

Riya logs whether she practised each day: 1 means she practised, 0 means she skipped. Print her longest streak (most consecutive 1s) and her current streak (consecutive 1s ending on the last day).

Input

First line: n. Second line: n values, each 0 or 1.

Output

Two numbers: longest current.

Constraints

Example 1

Input

8
1 1 0 1 1 1 0 1

Output

3 1

Example 2

Input

3
0 1 1

Output

2 2

Hints

  1. Keep a counter for the current run of 1s; a 0 resets it.
  2. The longest streak is the biggest value the counter ever reached; the current streak is the counter's value after the last day.

Approach

One pass. run is the number of consecutive 1s ending at the current day: add 1 on a 1, reset to 0 on a 0. Keep best = max(best, run). After the loop, best is the longest streak and run is the current streak, because it's the run that ends on the last day.

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 << " " << run << "\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, run)

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 + " " + run);
    }
}

Solve Practice Streak online · All practice problems