A16486 | $Prefix Max$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $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$ 能获得的最大价值。

输入 #1

输出 #1

C++ 编辑器

输入

输出