Beautiful Average

The trap here is thinking we need to inspect every subarray. We don't.

A subarray can have length $1$, so if the array contains some value $m$, we can choose just that one element and get average $m$.

Now let:

$M = \max_{1 \le i \le n} a_i$

Clearly, we can get average $M$ by taking the subarray containing only an occurrence of $M$.

So the answer is at least $M$.

Now we prove it can never be bigger.

Take any subarray of length $k$ with elements:

$x_1, x_2, \dots, x_k$

Since $M$ is the maximum element in the whole array, every element in this subarray satisfies:

$x_i \le M$

Therefore:

$x_1 + x_2 + \cdots + x_k \le kM$

Divide both sides by $k$:

$\frac{x_1+x_2+\cdots+x_k}{k} \le M$

That left side is exactly the average of the subarray. So no subarray average can exceed the maximum element of the array.

We already know a length-$1$ subarray can achieve that maximum, so the answer is exactly:

$\boxed{\max(a_1, a_2, \dots, a_n)}$

That's it. The constraints are tiny, but brute forcing all subarrays would be doing pushups in an elevator. Just print the max.

Algorithm

For each test case:

1. Read $n$.
2. Read the array.
3. Track the largest value.
4. Print it.

Complexity

For each test case, we scan the array once.

Time complexity: $O(n)$

Memory complexity: $O(1)$