你的任务是根据给定序列的大小(长度)选择最大的交替子序列(即下一个元素的符号与当前元素的符号相反，如正-负-正等，或负-正-负等)。在所有这些子序列中，你必须选择长度最大的子序列，并计算他的最大元素和。（即如果交替子序列的最大长度是 k ，那么你的任务就是找出某个长度为 k 的交替子序列的最大元素和。）
3156: 子序列
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 48
[提交][状态][讨论版][命题人:]
题目描述
输入描述
输入的第一行包含一个整数 t ( 1≤t≤104 )--测试用例数。然后是 t个测试用例。
测试用例的第一行包含一个整数 n( 1≤n≤2⋅105 ) - a 中的元素个数。第二行测试用例包含 n 个整数 a1,a2,…,an ( −109≤ai≤109,ai≠0 )
保证所有测试用例中 n的总和不超过 2⋅105 ( ∑n≤2⋅105 )。
测试用例的第一行包含一个整数 n( 1≤n≤2⋅105 ) - a 中的元素个数。第二行测试用例包含 n 个整数 a1,a2,…,an ( −109≤ai≤109,ai≠0 )
保证所有测试用例中 n的总和不超过 2⋅105 ( ∑n≤2⋅105 )。
输出描述
对于每个测试用例， 输出长度最大的交替子序列的最大和。
样例输入
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,2,3,−1,−2]（选了第三位第四位）。
在示例的第二个测试用例中，可能的答案之一是 [−1,−2,−1,−3]（选了第三位）
在示例的第三个测试用例中，答案是 [−2,8,3,8,−4,−15,5,−2,−3,1]（选了第一位，第四位，第五位，第七位，第八位，第十位）
在示例的第四个测试用例中，答案是 [1,−1000000000,1,−1000000000,1,−1000000000]。（全选）
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
cnt: 31481
关于网站改版