#3864. 小L的两个序列 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: chen_zhe

题目描述

小T给了小L一个序列,但是小L她现在想从里面选出两个序列。原序列为a1, a2... an,选出

                     t1     t2 
         d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n }
                     i=s1   j=s2

也就是选出两个不相交的连续序列,使得他们的和最大。

输入格式

本题有多组数据,第一行一个整数T,表示数据组数

下面T组数据,对于每一组数据:

第一行一个正整数n,表示小L的序列的长度。第二行n个整数,表示小L的序列

输出格式

对于每一组数据,输出正确答案

样例

#input

1
10
1 -1 2 2 3 -3 4 -4 5 -5

#output

13

#解释

其中一种最优的选法是:选择 2 2 3 -3 4和 5 这两个连续子序列。和为13

数据范围与提示

T <= 10

n <= 500000

序列中的每个数∈[-50, 50]