3. Concate and count

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Concate and count

时间限制:1s

空间限制:256MB

题目描述

有一个由 \(n\) 个非零整数组成的序列 \(a\) 。选择若干给定序列的子序列构成\(L\),要求\(L\)满足正负相间。输出长度最大的\(L\)的元素总和。如果长度最大的\(L\)不止一个,那么输出元素总和最大的那个。
正负相间是指 每个元素的符号都与它前一个元素的符号相反,如 \([+,-,+]\) ,或 \([-,+,-]\) 等等
元素总和是指 这个序列中,所有整数的和,如\([1,-1,2,-3]\)的元素总和是\(1+(-1)+2+(-3)=-1\).

数据格式

输入

第一行输入一个整数 \(t\) ,表示共有 \(t\) 组测试用例;

对于每个测试用例,第一行输入一个正整数 \(n\) ,表示数组 \(a\) 的长度;

接下来一行输入 \(n\) 个数字 \(a_1,a_2......a_i\ (1 \leq i \leq n)\) 表示数组 \(a\) 的元素。

输出

对于每个测试用例,输出一行一个整数,即最大正负相间的子序列的最大元素总和。

样例1

输入:

4
5
1 2 3 -1 -2
4
-1 -2 -1 -3
10
-2 8 3 8 -4 -15 5 -2 -3 1
6
1 -1000000000 1 -1000000000 1 -1000000000

输出:

2
-1
6
-2999999997

样例解释

  1. 在第一个样例中,选择的数据为 \([1,2,(3),(-1),-2]\) 。
  2. 在第二个样例中,选择的数据为 \([-1,-2,(-1),-3]\) 。
  3. 在第三个样例中,选择的数据为 \([(−2),8,3,(8),(−4),−15,(5),(−2),−3,(1)]\) 。
  4. 在第四个样例中,所有数据均选择。

数据范围及约定

测试点编号 约定 测试点分值
1~2 \(t=1,1 \leq n \leq 100,−100 \leq a_i \leq 100\) 每个测试点 10 分
3~4 \(t=1,1 \leq n \leq 2*10^5,−10^9 \leq a_i \leq 10^9\) 每个测试点 10 分
6~10 \(t \leq 10^4,1 \leq n \leq 2*10^5,−10^9 \leq a_i \leq 10^9\) 每个测试点 10 分

约定:对于所有测试用例,有 \(\sum{n} \leq 2 * 10^5\) 且 \(a_i≠0\) 。