【模板】双段最大子段和

题目描述

给定一个整数序列，请你找出 两个不重合的连续子段，使得这两个子段内所有数字的和最大。请计算这个最大和。

输入格式

第一行：一个整数 T（T≤30），表示数据组数。

接下来 T 组数据：

• 每组数据第一行：一个整数 n（2≤n≤50000），表示序列长度。
• 每组数据第二行：n 个整数 a1, a2, ..., an（|ai|≤10000）。

输出格式

对于每组数据，输出一个整数，即满足条件的最大和。

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

13

样例解释

对于样例中的序列 1 -1 2 2 3 -3 4 -4 5 -5，一种最优的选择是：

• 第一个连续子段：1 -1 2 2 3 -3 4，和为 1 + (-1) + 2 + 2 + 3 + (-3) + 4 = 8；
• 第二个连续子段：5，和为 5。

两个子段不重合，总和为 8 + 5 = 13，即为最大和。