1008. 恋恋的排列

题目描述

古明地恋在守矢神社闲逛时，注意到一排刻着整数的御柱。她可以发动一次无意识能力——将任意连续的一段御柱的顺序完全颠倒。她希望颠倒之后，从第一根开始累计的前缀和中，最大值尽可能大。你能帮她算出这个最大值吗？给定一个长度为 n 的整数序列 a1, a2, ..., an。你最多可以进行一次操

作：选择一个连续段 [l, r]，并将这段区间整体翻转，得到新序列 b。定义新序列的前缀和为： si = b1 + b2 + ... + bi，其中 1 <= i <= n

。 你的任务是：翻转至多一次后，所有前缀和 si 中的最大值，能达到

多少。

输入格式

第一行一个整数 T，表示测试数据组数。每组数据第一行一个整数 n，接下来一行 n 个整数 a1, a2, ..., an。

数据范围：

1 ≤ T ≤ 101 ≤ n ≤ 2 × 105−109 ≤ ai ≤ 109

答案保证在 64 位有符号整数范围内。

输出格式

对于每组测试用例，输出一行一个整数，表示答案。

样例输入

4
2
-100 200
4
-5 -4 -3 -2
5
1 -3 2 -1 4
6
10 -9 8 -7 6 -5

样例输出

200
-2
6
18

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）