题面#

You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$.

The value of an array is the sum of the maximums of each prefix of the array. More formally, the value of an array $a$ is $\sum_{i=1} ^{n} \operatorname{max}(a_1, \ldots, a_i)$. For example, the value of the array [$1, 2, 1$] is $\operatorname{max}(1) + \operatorname{max}(1, 2) + \operatorname{max}(1, 2, 1) = 1 + 2 + 2 = 5$.

You can choose two indices $i$ and $j$ and swap elements $a_i$ and $a_j$; this operation can be applied at most one time.

Find the maximum possible value of the array $a$ after at most one operation.

Input

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

The first line of each test case contains a single integer $n$ ($2 \le n \le 50$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^4$) — the array $a$.

Output

For each test case, output the maximum possible value of the array $a$ after the swap has been performed.

思路#

理清题目中的数组价值的含义为：

因此我们肯定需要一个函数来计算这个价值，我们将其命名为 get_v

由于题目要求的是交换任意一对索引之后的数组价值最大值，且交换操作只能执行一次，我们可以考虑暴力枚举进行

NOTE

为什么可以考虑暴力枚举？ 注意到 $2 \leq n \leq 50$，使得总方案数很小，所以时间复杂度可控

但是需要注意的是，在执行完调换的操作之后，需要将调换的元素进行还原，以免导致数组错乱引发的价值计算错误

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int get_v(std::vector<int> a) {
6
    int result = 0;
7
    for (int i = 0; i < a.size(); i ++) {
8
        int mx = a[i];
9
        for (int j = 0; j <= i; j ++) {
10
            if (a[j] > mx) mx = a[j];
11
        }
12
        result += mx;
13
    }
14
    return result;
15
}
16

17
int main() {
18
    int t;
19
    cin >> t;
20
    while (t --) {
21
        int n;
22
        cin >> n;
23
        vector<int> a(n);
24
        for (int i = 0; i < n; i ++) cin >> a[i];
25

26
        int ans = get_v(a);
27

28
        for (int i = 0; i < n; i ++) {
29
            for (int j = i + 1; j < n; j ++) {
30
                int tmp = a[i], ri = 0, rj = 0;
31
                a[i] = a[j];
32
                a[j] = tmp;
33
                ans = max(ans, get_v(a));
34
                a[i] = ri; a[j] = rj;
35
            }
36
        }
37
        cout << ans << endl;
38
    }
39
}