CF2274B Prefix

给定一个数组 $a_1, a_2, \ldots, a_n$。 对于每个下标 $i=2,3,\ldots,n$，按照顺序执行如下操作： - 令 $s = a_1 + a_2 + \ldots + a_{i-1}$。 - 将 $a_i$ 替换为以下三个值之一：$a_i - s$，$a_i$，或 $a_i + s$。 在所有可能的选择中，求经过上述过程后 $\max(a_1, a_2, \ldots, a_n)$ 的最大值。

每组测试数据包含多组测试用例。第一行包含测试用例组数 $t$（$1 \le t \le 10^4$）。 接下来每组测试用例描述如下： 每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 50$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-50 \le a_i \le 50$）。

对于每组测试用例，输出一个整数，表示最终可能得到的 $\max(a_1, a_2, \ldots, a_n)$ 的最大值。 请注意，对于某些测试用例，答案可能无法用 $32$ 位整型表示，请在你的编程语言中使用至少 $64$ 位整数类型（例如 C++ 里的 long long）。

在第一个测试用例中，最后的数组可以变为 $[3, -8, -4, -13, 24]$，因此答案为 $24$。 在第二个测试用例中，对于 $i=2$，有 $s=a_1=-1$。将 $a_2$ 替换为 $a_2-s=2-(-1)=3$，因此答案为 $3$。 在第三个测试用例中，最终的数组可以变为 $[1, 3, 7]$，因此答案为 $7$。 在第四个测试用例中，将 $a_2$ 替换为 $a_2+s=-4$，得到 $s=-6$，对于 $i=3$，将 $a_3$ 替换为 $a_3-s=-2-(-6)=4$，最终数组为 $[-2, -4, 4]$，因此答案为 $4$。 由 ChatGPT 5 翻译