Interesting Sum

题意翻译

给定一个长度为 $n$ 的序列 $a$，令 $s=\max(a_1,a_2,\dots,a_{l-1},a_{r+1},\dots,a_{n-1},a_n)-\min(a_1,a_2,\dots,a_{l-1},a_{r+1},\dots,a_{n-1},a_n)+\max(a_l,a_{l+1},\dots,a_{r-1},a_r)-\min(a_l,a_{l+1},\dots,a_{r-1},a_r)$，要求选定一个区间 $[l,r]$，使得 $s$ 最大，输出 $s$。 Translated by @_JYqwq_

题目描述

You are given an array $ a $ that contains $ n $ integers. You can choose any proper subsegment $ a_l, a_{l + 1}, \ldots, a_r $ of this array, meaning you can choose any two integers $ 1 \le l \le r \le n $ , where $ r - l + 1 < n $ . We define the beauty of a given subsegment as the value of the following expression: $$\max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}). $$ Please find the maximum beauty among all proper subsegments.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. Then follow the descriptions of each test case. The first line of each test case contains a single integer $ n $ $ (4 \leq n \leq 10^5) $ — the length of the array. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq 10^9 $ ) — the elements of the given array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each testcase print a single integer — the maximum beauty of a proper subsegment.

输入输出样例

输入样例 #1

4
8
1 2 2 3 1 5 6 1
5
1 2 3 100 200
4
3 3 3 3
6
7 8 3 1 1 8

输出样例 #1

9
297
0
14

说明

In the first test case, the optimal segment is $ l = 7 $ , $ r = 8 $ . The beauty of this segment equals to $ (6 - 1) + (5 - 1) = 9 $ . In the second test case, the optimal segment is $ l = 2 $ , $ r = 4 $ . The beauty of this segment equals $ (100 - 2) + (200 - 1) = 297 $ .

题目大意：
给定一个长度为 $n$ 的序列 $a$，从中选择一个子段 $a_l, a_{l+1}, \ldots, a_r$，使得表达式的值最大：
$$\max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}).$$
输出最大的表达式的值。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 $n$（$4 \leq n \leq 10^5$）——数组的长度。
- 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_{i} \leq 10^9$）——给定数组的元素。

输出格式：
- 对于每个测试用例，打印一个整数——一个合适的子段的最大美感值。

输入输出样例：
输入样例 #1：
```
4
8
1 2 2 3 1 5 6 1
5
1 2 3 100 200
4
3 3 3 3
6
7 8 3 1 1 8
```
输出样例 #1：
```
9
297
0
14
```题目大意： 给定一个长度为 $n$ 的序列 $a$，从中选择一个子段 $a_l, a_{l+1}, \ldots, a_r$，使得表达式的值最大： $$\max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}).$$ 输出最大的表达式的值。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 $n$（$4 \leq n \leq 10^5$）——数组的长度。 - 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_{i} \leq 10^9$）——给定数组的元素。 输出格式： - 对于每个测试用例，打印一个整数——一个合适的子段的最大美感值。 输入输出样例： 输入样例 #1： ``` 4 8 1 2 2 3 1 5 6 1 5 1 2 3 100 200 4 3 3 3 3 6 7 8 3 1 1 8 ``` 输出样例 #1： ``` 9 297 0 14 ```