Решение задачи Чередующаяся подпоследовательность с Codeforces

Напомним, что последовательность b является подпоследовательностью последовательности a, если b может быть получена из a путем удаления нуля или более элементов без изменения порядка оставшихся элементов. Например, если a=[1,2,1,3,1,2,1], то возможные подпоследовательности: [1,1,1,1], [3] и [1,2,1,3,1,2,1], но не [3,2,3] и [1,1,1,1,2].

Вам задана последовательность a, состоящая из n положительных и отрицательных элементов (в последовательности нет нулей).

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

Другими словами, если максимальная длина чередующейся подпоследовательности равна k, то ваша задача — найти максимальную сумму элементов какой-то чередующейся подпоследовательности длины k.

Вам нужно ответить на t независимых наборов тестовых данных.