← 返回题目列表

Codeforces · 1654/A

A. 最大的蛋糕美味

中文机器翻译题面 查看原题

一条线上有 $$$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}、\点、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_i$$$ 是第 $$$i$$$ 块蛋糕的重量。

输出

对于每个测试用例,打印一个整数:最多执行一次操作后蛋糕的最大美味度。

示例

输入 #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

输出 #1

12
156
160
1998673
2000000000

注意

在第一个测试用例中,反转子段 $$$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$$$ 的。