Mainak and Array

题意翻译

### 题目大意 给定一个长度为 $n$ 的数组 $a$，可以选定**一个**区间 $[l, \; r]$ 进行**恰好一次**操作，求操作后最大的 $a_n - a_1$。 操作方法：选定区间 $[l, \; r]$ 和旋转次数 $k$, 每次旋转为 $a_l = a_{l + 1}, \; a_{l + 1} = a_{l + 2}, \; \dots, \; a_{r - 1} = a_r, \; a_r = a_l$ ### 输入格式 第一行一个整数 $T \; (1 \leqslant T \leqslant 50)$，表示测试样例组数。 对于每组测试样例，第一行为一个整数 $n \; (1 \leqslant n \leqslant 2000)$ 表示数组长度。 接下来的一行含有 $n$ 个整数 $a_i \; (1 \leqslant a_i \leqslant 999)$，表示该数组。 数据保证 $\sum n \leqslant 2000$。 ### 输出格式 对于每组测试样例包含一行一个整数，表示最大的 $a_n - a_1$。 $Translated \; by \; Zigh$

题目描述

Mainak has an array $ a_1, a_2, \ldots, a_n $ of $ n $ positive integers. He will do the following operation to this array exactly once: - Pick a subsegment of this array and cyclically rotate it by any amount. Formally, he can do the following exactly once:- Pick two integers $ l $ and $ r $ , such that $ 1 \le l \le r \le n $ , and any positive integer $ k $ . - Repeat this $ k $ times: set $ a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l $ (all changes happen at the same time). Mainak wants to maximize the value of $ (a_n - a_1) $ after exactly one such operation. Determine the maximum value of $ (a_n - a_1) $ that he can obtain.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 50 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2000 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 999 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .

输出格式

For each test case, output a single integer — the maximum value of $ (a_n - a_1) $ that Mainak can obtain by doing the operation exactly once.

输入输出样例

输入样例 #1

5
6
1 3 9 11 5 7
1
20
3
9 99 999
4
2 1 8 1
3
2 1 5

输出样例 #1

10
0
990
7
4

说明

- In the first test case, we can rotate the subarray from index $ 3 $ to index $ 6 $ by an amount of $ 2 $ (i.e. choose $ l = 3 $ , $ r = 6 $ and $ k = 2 $ ) to get the optimal array: $ $[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}] $ $ So the answer is $ a\_n - a\_1 = 11 - 1 = 10 $ .</li><li> In the second testcase, it is optimal to rotate the subarray starting and ending at index $ 1 $ and rotating it by an amount of $ 2 $ .</li><li> In the fourth testcase, it is optimal to rotate the subarray starting from index $ 1 $ to index $ 4 $ and rotating it by an amount of $ 3 $ . So the answer is $ 8 - 1 = 7$.