Подотрезок — это непрерывная часть массива.
Ярик недавно нашёл массив $$$a$$$ из $$$n$$$ элементов, и ему стало очень интересно найти сумму непустого подотрезка с максимальной суммой. Но Ярик не любит числа одной чётности, стоящие рядом, так что у подотрезка, который он выберет, чётности соседних элементов должны различаться.
Например, массив $$$[1, 2, 3]$$$ подойдёт, но $$$[1, 2, 4]$$$ не подойдёт, так как $$$2$$$ и $$$4$$$ — чётные числа и стоят рядом.
Вам нужно помочь Ярику и вывести максимальную сумму такого подотрезка.
Первая строка содержит одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ —количество наборов входных данных. Далее следуют описания этих наборов.
В первой строке дано одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — длина массива.
Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(-10^3 \le a_i \le 10^3)$$$ — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора данных выведите одно число — ответ на задачу.
751 2 3 4 549 9 8 86-1 4 -1 0 5 -44-1 2 4 -31-10003101 -99 10120-10 5 -8 10 6 -10 7 9 -2 -6 7 2 -4 6 -1 7 -6 -7 4 1
15 17 8 4 -1000 101 10
| Codeforces Round 909 (Div. 3) |
|---|
| Закончено |
