309695: CF1720B. Interesting Sum

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 $ .

Input

题意翻译

给定一个长度为 $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_

Output

题目大意:
给定一个长度为 $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 ```

加入题单

上一题 下一题 算法标签: