Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Ваша задача — разбить $$$a$$$ на непустые подотрезки (всего существует $$$2^{n-1}$$$ таких разбиений).
Пусть $$$s=a_l+a_{l+1}+\ldots+a_r$$$. Значение подмассива $$$a_l, a_{l+1}, \ldots, a_r$$$ равно:
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — количество наборов входных данных. Далее следует их описание.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальную сумму значений подотрезков, которую можно получить при оптимальном разбиении.
531 2 -340 -2 3 -45-1 -2 3 -1 -16-1 2 -3 4 -5 671 -1 -1 1 -1 -1 1
1 2 1 6 -1
Пример $$$1$$$: одно из оптимальных разбиений выглядит так: $$$[1, 2]$$$, $$$[-3]$$$. $$$1+2>0$$$, поэтому величина $$$[1, 2]$$$ равна $$$2$$$. $$$-3<0$$$, поэтому величина $$$[-3]$$$ равна $$$-1$$$. $$$2+(-1)=1$$$.
Пример $$$2$$$: возможное оптимальное разбиение выглядит так: $$$[0, -2, 3]$$$, $$$[-4]$$$, сумма величин подотрезков равна $$$3+(-1)=2$$$.
| Codeforces Round 783 (Div. 2) |
|---|
| Закончено |
