Задача . C. Чередующаяся подпоследовательность

Напомним, что последовательность \(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\) независимых наборов тестовых данных.