题目描述

有 $n$ 块蛋糕排成一行，第 $i$ 块蛋糕的重量为 $a_i$（$1 \leq i \leq n$）。

蛋糕的美味度定义为相邻两块蛋糕的总重量的最大值，即 $\max(a_1+a_2,\, a_2+a_3,\, \ldots,\, a_{n-1} + a_{n})$。

你希望最大化蛋糕的美味度。你最多可以进行一次如下操作（多于一次会毁掉蛋糕）：

• 选择一段连续的子区间 $a[l, r]$（$1 \leq l \leq r \leq n$），将其反转。

数组 $a$ 的子区间 $a[l, r]$ 指的是序列 $a_l, a_{l+1}, \dots, a_r$。

如果你将其反转，数组将变为 $a_1, a_2, \dots, a_{l-2}, a_{l-1}, \underline{a_r}, \underline{a_{r-1}}, \underline{\dots}, \underline{a_{l+1}}, \underline{a_l}, a_{r+1}, a_{r+2}, \dots, a_{n-1}, a_n$。

例如，若初始重量为 $[5, 2, 1, 4, 7, 3]$，你可以反转子区间 $a[2, 5]$，得到 $[5, \underline{7}, \underline{4}, \underline{1}, \underline{2}, 3]$。此时蛋糕的美味度为 $5 + 7 = 12$（操作前美味度为 $4+7=11$）。

请你求出最多进行一次操作后，蛋糕的最大美味度。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 50$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 1000$），表示蛋糕的块数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每块蛋糕的重量。

输出格式

对于每个测试用例，输出一个整数，表示最多进行一次操作后蛋糕的最大美味度。

说明/提示

在第一个测试用例中，反转子区间 $a[2, 5]$ 后，蛋糕的重量为 $[5, \underline{7}, \underline{4}, \underline{1}, \underline{2}, 3]$。此时美味度为 $\max(5+7, 7+4, 4+1, 1+2, 2+3) = 12$。这是最多进行一次操作后能获得的最大美味度。

在第二个测试用例中，最优策略是不进行任何操作。美味度为 $78+78 = 156$。

在第三个测试用例中，反转子区间 $a[1, 2]$ 后，蛋糕的重量为 $[\underline{54}, \underline{69}, 91]$。此时美味度为 $\max(54+69, 69+91) = 160$。进行最多一次操作无法使美味度超过 $160$。

由 ChatGPT 4.1 翻译

样例

5
6
5 2 1 4 7 3
3
32 78 78
3
69 54 91
8
999021 999021 999021 999021 999652 999021 999021 999021
2
1000000000 1000000000

12
156
160
1998673
2000000000