TEMPPLANT - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

The temperature on the i-th of the next N days is A_i.
A plant needs two consecutive days to grow. Its height will be the lower temperature among the two days.
Find the maximum possible height the plant can grow to.

EXPLANATION:

If the plant grows on days i and i+1, it will grow to a height of \min(A_i, A_{i+1}).

We want the maximum possible height, so the answer is the maximum of

\min(A_1, A_2), \min(A_2, A_3), \ldots, \min(A_{N-1}, A_N)

This can be found in \mathcal{O}(N) time: compute all the values of the form \min(A_i, A_{i+1}) and then print the maximum among them.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

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