题目描述
一条地铁线路上依次记录了 $n$ 个时间片的客流变化量（可为负）。调度中心要选出两段不重叠的连续时间片，使两段变化量之和最大（两段都必须非空，第一段整体在第二段之前）。
求这个最大总和。共 $T$ 组数据。
输入格式
第一行整数 $T$。 每组数据：第一行整数 $n$；第二行 $n$ 个整数，为各时间片的客流变化量。
输出格式
$T$ 行，每行一个整数：两段不重叠连续子段的最大总和。
数据范围
$$T \le 30,\quad 2 \le n \le 9000,\quad |a_i| \le 10000$$