STREAK - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: tanminati
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given the number of problems solved by TanMinati on each of N days, the count on the i-th day being A_i.
Find the longest coding streak, i.e. a sequence of days such that at least one problem was solved every day.

EXPLANATION:

Since N is quite small, a simple nested loop solution is already fast enough here.
That is, fix L and R (1 \le L \le R \le N) to be the boundaries of the streak, and then check if A_i \gt 0 for each L \le i \le R.

It’s also possible to solve the problem in \mathcal{O}(N) time, with the following algorithm:

  • Let \text{cur} be a variable denoting the current streak.
  • Iterate i = 1, 2, 3, \ldots, N in order. Then, at index i,
    • If A_i = 0, the current streak ends.
      Set \text{cur} = 0.
    • If A_i \gt 0 instead, the current streak extends by 1.
      Set \text{cur} \to \text{cur} + 1.
  • The answer is then the maximum value ever reached by \text{cur}.

TIME COMPLEXITY:

\mathcal{O}(N) to \mathcal{O}(N^3) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    cur, ans = 0, 0
    for i in range(n):
        if a[i] == 0: cur = 0
        else: cur += 1
        ans = max(ans, cur)
    print(ans)