Две версии этой задачи отличаются друг от друга. Возможно, вы захотите прочитать обе версии. Вы сможете делать взломы, только если обе версии решены.
Вам дан массив \(a\) длины \(n\). Изначально \(c = 0\). Для каждого \(i\) от \(1\) до \(n\) (в порядке возрастания) выполните ровно одно из следующих действий:
- Вариант \(1\): сделать \(c\) равным \(c + a_i\).
- Вариант \(2\): сделать \(c\) равным \(|c + a_i|\), где \(|x|\) — абсолютное значение \(x\).
Пусть максимальное возможное конечное значение \(c\) после описанной выше процедуры равно \(k\). Найдите \(k\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — значение \(k\).
Примечание
В первом наборе входных данных, если при каждом прибавлении брать абсолютное значение \(c\), то в итоге получится \(6\). Можно показать, что это максимальный результат.
Во втором наборе входных данных присвоение абсолютного значения ничего не изменит, поэтому мы можем просто просуммировать массив, ничего не делая, чтобы получить \(24\).
В третьем наборе входных данных оптимально взять абсолютное значение \(c\) только один раз в конце, в результате чего мы получим ответ \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
6
24
6
4000000000
22
|