CF1654A.Maximum Cake Tastiness

There are $n$ pieces of cake on a line. The $i$-th piece of cake has weight $a_i$ ($1 \leq i \leq n$).

The tastiness of the cake is the maximum total weight of two adjacent pieces of cake (i. e., $\max(a_1+a_2,\, a_2+a_3,\, \ldots,\, a_{n-1} + a_{n})$).

You want to maximize the tastiness of the cake. You are allowed to do the following operation at most once (doing more operations would ruin the cake):

• Choose a contiguous subsegment $a[l, r]$ of pieces of cake ($1 \leq l \leq r \leq n$), and reverse it.

The subsegment $a[l, r]$ of the array $a$ is the sequence $a_l, a_{l+1}, \dots, a_r$.

If you reverse it, the array will become $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$.

For example, if the weights are initially $[5, 2, 1, 4, 7, 3]$, you can reverse the subsegment $a[2, 5]$, getting $[5, \underline{7}, \underline{4}, \underline{1}, \underline{2}, 3]$. The tastiness of the cake is now $5 + 7 = 12$ (while before the operation the tastiness was $4+7=11$).

Find the maximum tastiness of the cake after doing the operation at most once.

一条直线上有 $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$）。

求在最多执行一次上述操作后，蛋糕所能达到的最大美味度。

The first line contains a single integer $t$ ($1 \le t \le 50$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 1000$) — the number of pieces of cake.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — $a_i$ is the weight of the $i$-th piece of cake.

第一行包含一个整数 $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_i$ 表示第 $i$ 块蛋糕的重量。

For each test case, print a single integer: the maximum tastiness of the cake after doing the operation at most once.

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

In the first test case, after reversing the subsegment $a[2, 5]$, you get a cake with weights $[5, \underline{7}, \underline{4}, \underline{1}, \underline{2}, 3]$. The tastiness of the cake is now $\max(5+7, 7+4, 4+1, 1+2, 2+3) = 12$. This is the maximum possible tastiness of the cake one can obtain by performing the operation at most once.

In the second test case, it's optimal not to do any operation. The tastiness is $78+78 = 156$.

In the third test case, after reversing the subsegment $a[1, 2]$, you get a cake with weights $[\underline{54}, \underline{69}, 91]$. The tastiness of the cake is now $\max(54+69, 69+91) = 160$. There is no way to make the tastiness of the cake greater than $160$ by performing at most one operation.

在第一个测试用例中，将子段 $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$。