Задача - 1984C1

Codeforces Global Round 26
Закончено

→ Виртуальное участие

Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований. Если вы раньше видели эти задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве. Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве. Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.

→ Теги задачи

дп

жадные алгоритмы

математика

*1300

Нет прав на редактирование

Две версии этой задачи отличаются друг от друга. Возможно, вы захотите прочитать обе версии. Вы сможете делать взломы, только если обе версии решены.

Вам дан массив $a$ длины $n$ . Изначально $c = 0$ . Для каждого $i$ от $1$ до $n$ (в порядке возрастания) выполните ровно одно из следующих действий:

Вариант $1$ : сделать $c$ равным $c + a_i$ .
Вариант $2$ : сделать $c$ равным $|c + a_i|$ , где $|x|$ — абсолютное значение $x$ .

Пусть максимальное возможное конечное значение $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$ .

Пример

Входные данные

5
4
10 -9 -3 4
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4

Выходные данные

Примечание

В первом наборе входных данных, если при каждом прибавлении брать абсолютное значение $c$ , то в итоге получится $6$ . Можно показать, что это максимальный результат.

Во втором наборе входных данных присвоение абсолютного значения ничего не изменит, поэтому мы можем просто просуммировать массив, ничего не делая, чтобы получить $24$ .

В третьем наборе входных данных оптимально взять абсолютное значение $c$ только один раз в конце, в результате чего мы получим ответ $6$ .

Соревнования по программированию 2.0

Время на сервере: 13.03.2025 08:41:11 (h1).

Десктопная версия, переключиться на мобильную.

При поддержке