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
- 1 ≤ n ≤ 10^5
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
- Keep a counter for the current run of 1s; a 0 resets it.
- 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);
}
}