← 返回题目列表

Codeforces · 2185/B

B. 前缀最大

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

给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$。

数组的值是数组每个前缀的最大值之和。更正式地说,数组 $$$a$$$ 的值为 $$$\sum_{i=1} ^{n} \operatorname{max}(a_1, \ldots, a_i)$$$。例如,数组 [$$$1, 2, 1$$$] 的值为 $$$\operatorname{max}(1) + \operatorname{max}(1, 2) + \operatorname{max}(1, 2, 1) = 1 + 2 + 2 = 5$$$。

您可以选择两个索引$$$i$$$和$$$j$$$并交换元素$$$a_i$$$和$$$a_j$$$;可以应用此操作 最多 一次。

最多执行一次操作后找出数组 $$$a$$$ 的最大可能值。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — 数组 $$$a$$$。

输出

对于每个测试用例,在执行交换后输出数组 $$$a$$$ 的最大可能值。

示例

输入
复制

4
5
2 1 4 5 3
2
5 1
3
3 2 1
2
6 7

输出
复制

25
10
9
14

注意

对于第一个测试用例,我们可以将 $$$a_1$$$ 与 $$$a_4$$$ 交换以获得数组 [$$$5, 1, 4, 2, 3$$$],其值为 $$$\operatorname{max}(5) + \operatorname{max}(5, 1) + \operatorname{max}(5, 1, 4) + \operatorname{max}(5, 1, 4, 2) + \operatorname{max}(5, 1, 4, 2, 3) = 25$$$。

对于第二个测试用例,数组的当前值为 $$$\operatorname{max}(5) + \operatorname{max}(5, 1) = 10$$$。如果我们要交换 $$$a_1$$$ 和 $$$a_2$$$,$$$a$$$ 将等于 [$$$1, 5$$$],其值为 $$$\operatorname{max}(1) + \operatorname{max}(1, 5) = 6$$$,这意味着最好的选择是不执行交换。