G-最大子段和，但是两段_河南萌新联赛2025第（一）场：河南工业大学

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

注意本题数据量大，C++ 选手请关闭流同步：

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

给定长度为 $n$ 的整数数组 $a$ ，从中选择两个非空、连续、不重叠的子段。使这两个子段中元素之和最大。

用数学语言描述：

选择区间 $[l_1, r_1]$ 和 $[l_2, r_2]$ ，满足

$S_1 = \sum_{i=l_1}^{r_1} a_i,\quad S_2 = \sum_{i=l_2}^{r_2} a_i.$

计算最大子段和 $S_1+S_2$ 。

第一行只有一个整数 ，表示测试数据的组数。

接下来每组测试数据包含两行：

第一行一个整数  表示数组长度。

第二行  个用空格分开的整数 ，表示数组  的每个元素。

数据规模：

对每组测试数据，在一行中输出一个整数，表示两个不重叠连续子段元素之和最大值。

示例1

复制

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

复制

9
-3

样例 1：在数组  上取区间  和子段 ，总和为 。

样例 2：在数组  上取区间  和子段 ，总和为 。