Codeforces Global Round 26 |
---|
Закончено |
Две версии этой задачи отличаются друг от друга. Возможно, вы захотите прочитать обе версии. Вы сможете делать взломы, только если обе версии решены.
Вам дан массив $$$a$$$ длины $$$n$$$. Изначально $$$c = 0$$$. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ (в порядке возрастания) выполните ровно одно из следующих действий:
Пусть максимальное возможное конечное значение $$$c$$$ после описанной выше процедуры равно $$$k$$$. Найдите $$$k$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$).
Вторая строка каждого случая содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$\ldots$$$, $$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — значение $$$k$$$.
5410 -9 -3 481 4 3 4 1 4 3 43-1 -2 -34-1000000000 1000000000 1000000000 100000000041 9 8 4
6 24 6 4000000000 22
В первом наборе входных данных, если при каждом прибавлении брать абсолютное значение $$$c$$$, то в итоге получится $$$6$$$. Можно показать, что это максимальный результат.
Во втором наборе входных данных присвоение абсолютного значения ничего не изменит, поэтому мы можем просто просуммировать массив, ничего не делая, чтобы получить $$$24$$$.
В третьем наборе входных данных оптимально взять абсолютное значение $$$c$$$ только один раз в конце, в результате чего мы получим ответ $$$6$$$.
Название |
---|