Editorial for Circus 2

Approach

Use two pointers, one at each end of the array.

At any step, the current pair of posts gives excitement factor $(r - l) \cdot \min(a_l, a_r)$. Record that value, then move the pointer pointing to the shorter post inward:

• if $a_l \le a_r$, increment $l$;
• otherwise, decrement $r$.

Why is this safe? Suppose $a_l \le a_r$. Any pair that keeps the same left post $l$ but moves the right post inward has smaller distance, and its minimum height is still at most $a_l$. So no such pair can beat the current one. That means the left pointer can be discarded safely.

Each pointer moves at most $n$ times, so the algorithm runs in $O(n)$ time.

Solution (Python)

n = int(input())
a = list(map(int, input().split()))

l = 0
r = n - 1
ans = 0

while l < r:
    ans = max(ans, (r - l) * min(a[l], a[r]))
    if a[l] <= a[r]:
        l += 1
    else:
        r -= 1

print(ans)