CF1720B Interesting Sum

给定一个包含 $n$ 个整数的数组 $a$。你可以选择该数组的任意一个真子区间 $a_l, a_{l + 1}, \ldots, a_r$，即可以选择任意满足 $1 \le l \le r \le n$ 且 $r - l + 1 < n$ 的两个整数 $l$ 和 $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$）——给定数组的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示真子区间的最大美丽值。

在第一个测试用例中，最优的区间是 $l = 7$，$r = 8$。该区间的美丽值为 $(6 - 1) + (5 - 1) = 9$。 在第二个测试用例中，最优的区间是 $l = 2$，$r = 4$。该区间的美丽值为 $(100 - 2) + (200 - 1) = 297$。 由 ChatGPT 4.1 翻译