题目描述

给定一个长度为 $n$ 的整数序列 $a$，请从中选出两个不重叠的非空连续子段，使两个子段内所有元素的总和最大。

设两个子段分别为 $[s_1,t_1]$ 和 $[s_2,t_2]$，必须满足 $1\le s_1\le t_1<s_2\le t_2\le n$。两个子段可以相邻，也可以在它们之间留有未选中的元素。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

接下来依次给出 $T$ 组数据，每组数据的格式如下：

• 第一行包含一个整数 $n$，表示序列的长度。
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，相邻整数之间用空格分隔。

输出格式

对于每组数据，输出一行一个整数，表示两个不重叠的非空连续子段的最大总和。

样例

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

13

样例解释

选取第 $3$ 至第 $7$ 个元素和第 $9$ 个元素，两个子段分别为 $[2,2,3,-3,4]$ 和 $[5]$，总和为 $8+5=13$。

数据范围与提示

• $1\le T\le 30$
• $2\le n\le 50000$
• $|a_i|\le 10000$

来源

POJ 2479 Maximum sum