Вам дан массив $$$a$$$ длины $$$n$$$.
Ваша задача — найти максимальное возможное среднее значение любого подмассива$$$^{\text{∗}}$$$ массива $$$a$$$.
Формально, для любых индексов $$$l, r$$$ таких, что $$$1 \le l \le r \le n$$$, среднее значение подмассива $$$a_l, a_{l+1}, \dots, a_r$$$ определяется как сумма элементов, делённая на их количество или: $$$$$$\texttt{avg}(l,r) = \frac{1}{r-l+1} \sum_{i=l}^{r} a_i$$$$$$ Выведите максимальное значение $$$\texttt{avg}(l,r)$$$ для всех выборов $$$l, r$$$.
$$$^{\text{∗}}$$$Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ путем удаления нескольких (возможно, нуля или всех) элементов с начала и нескольких (возможно, нуля или всех) элементов с конца. В частности, массив является подмассивом самого себя.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10$$$) — длина массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10$$$) — элементы массива.
Для каждого набора входных данных выведите одно целое число — максимальное среднее значение любого подмассива данного массива.
Можно показать, что ответ всегда является целым числом.
343 3 3 357 1 6 9 953 4 4 4 3
394
| Codeforces Round 1059 (Div. 3) |
|---|
| Закончено |
