309729: CF1726A. Mainak and Array
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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$.Input
题意翻译
### 题目大意 给定一个长度为 $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$Output
**题目大意**
给定一个长度为 $ n $ 的数组 $ a $，可以选定**一个**区间 $[l, r]$ 进行**恰好一次**操作，求操作后最大的 $ a_n - a_1 $。
操作方法：选定区间 $[l, r]$ 和旋转次数 $ k $，每次旋转为 $ a_l = a_{l + 1}, a_{l + 1} = a_{l + 2}, \ldots, 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 $。
**题目描述**
Mainak 拥有一个由 $ n $ 个正整数组成的数组 $ a_1, a_2, \ldots, a_n $。他将对此数组执行一次以下操作：
- 选择数组的一个子段并循环旋转任意次数。
形式上，他可以执行以下操作恰好一次：
- 选择两个整数 $ l $ 和 $ r $，使得 $ 1 \le l \le r \le n $，以及任意正整数 $ k $。
- 重复此操作 $ k $ 次：设置 $ a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l $（所有更改同时发生）。
Mainak 想要通过恰好一次这样的操作来最大化 $ (a_n - a_1) $ 的值。确定他可以获得的最大 $ (a_n - a_1) $ 值。
**输入输出格式**
**输入格式**
- 每个测试包含多个测试用例。第一行包含一个整数 $ t \; (1 \le t \le 50) $ —— 测试用例的数量。测试用例的描述如下。
- 每个测试用例的第一行包含一个整数 $ n \; (1 \le n \le 2000) $。
- 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n \; (1 \le a_i \le 999) $。
- 保证所有测试用例的 $ n $ 之和不超过 $ 2000 $。
**输出格式**
- 对于每个测试用例，输出一个整数 —— Mainak 通过恰好一次操作可以获得的最大 $ (a_n - a_1) $ 值。
**输入输出样例**
**输入样例 #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
```
**说明**
- 在第一个测试用例中，我们可以将下标从 3 到 6 的子数组旋转 2 次（即选择 $ l = 3 $, $ r = 6 $ 和 $ k = 2 $）以得到最优数组：$$
[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}]
$$ 因此答案是 $ a_n - a_1 = 11 - 1 = 10 $。
- 在第二个测试用例中，最优的做法是旋转下标从 1 到 1 的子数组 2 次。
- 在第四个测试用例中，最优的做法是旋转下标从 1 到 4 的子数组 3 次。所以答案是 $ 8 - 1 = 7 $。**题目大意** 给定一个长度为 $ n $ 的数组 $ a $，可以选定**一个**区间 $[l, r]$ 进行**恰好一次**操作，求操作后最大的 $ a_n - a_1 $。 操作方法：选定区间 $[l, r]$ 和旋转次数 $ k $，每次旋转为 $ a_l = a_{l + 1}, a_{l + 1} = a_{l + 2}, \ldots, 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 $。 **题目描述** Mainak 拥有一个由 $ n $ 个正整数组成的数组 $ a_1, a_2, \ldots, a_n $。他将对此数组执行一次以下操作： - 选择数组的一个子段并循环旋转任意次数。 形式上，他可以执行以下操作恰好一次： - 选择两个整数 $ l $ 和 $ r $，使得 $ 1 \le l \le r \le n $，以及任意正整数 $ k $。 - 重复此操作 $ k $ 次：设置 $ a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l $（所有更改同时发生）。 Mainak 想要通过恰好一次这样的操作来最大化 $ (a_n - a_1) $ 的值。确定他可以获得的最大 $ (a_n - a_1) $ 值。 **输入输出格式** **输入格式** - 每个测试包含多个测试用例。第一行包含一个整数 $ t \; (1 \le t \le 50) $ —— 测试用例的数量。测试用例的描述如下。 - 每个测试用例的第一行包含一个整数 $ n \; (1 \le n \le 2000) $。 - 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n \; (1 \le a_i \le 999) $。 - 保证所有测试用例的 $ n $ 之和不超过 $ 2000 $。 **输出格式** - 对于每个测试用例，输出一个整数 —— Mainak 通过恰好一次操作可以获得的最大 $ (a_n - a_1) $ 值。 **输入输出样例** **输入样例 #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 ``` **说明** - 在第一个测试用例中，我们可以将下标从 3 到 6 的子数组旋转 2 次（即选择 $ l = 3 $, $ r = 6 $ 和 $ k = 2 $）以得到最优数组：$$ [1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}] $$ 因此答案是 $ a_n - a_1 = 11 - 1 = 10 $。 - 在第二个测试用例中，最优的做法是旋转下标从 1 到 1 的子数组 2 次。 - 在第四个测试用例中，最优的做法是旋转下标从 1 到 4 的子数组 3 次。所以答案是 $ 8 - 1 = 7 $。
给定一个长度为 $ n $ 的数组 $ a $，可以选定**一个**区间 $[l, r]$ 进行**恰好一次**操作，求操作后最大的 $ a_n - a_1 $。
操作方法：选定区间 $[l, r]$ 和旋转次数 $ k $，每次旋转为 $ a_l = a_{l + 1}, a_{l + 1} = a_{l + 2}, \ldots, 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 $。
**题目描述**
Mainak 拥有一个由 $ n $ 个正整数组成的数组 $ a_1, a_2, \ldots, a_n $。他将对此数组执行一次以下操作：
- 选择数组的一个子段并循环旋转任意次数。
形式上，他可以执行以下操作恰好一次：
- 选择两个整数 $ l $ 和 $ r $，使得 $ 1 \le l \le r \le n $，以及任意正整数 $ k $。
- 重复此操作 $ k $ 次：设置 $ a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l $（所有更改同时发生）。
Mainak 想要通过恰好一次这样的操作来最大化 $ (a_n - a_1) $ 的值。确定他可以获得的最大 $ (a_n - a_1) $ 值。
**输入输出格式**
**输入格式**
- 每个测试包含多个测试用例。第一行包含一个整数 $ t \; (1 \le t \le 50) $ —— 测试用例的数量。测试用例的描述如下。
- 每个测试用例的第一行包含一个整数 $ n \; (1 \le n \le 2000) $。
- 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n \; (1 \le a_i \le 999) $。
- 保证所有测试用例的 $ n $ 之和不超过 $ 2000 $。
**输出格式**
- 对于每个测试用例，输出一个整数 —— Mainak 通过恰好一次操作可以获得的最大 $ (a_n - a_1) $ 值。
**输入输出样例**
**输入样例 #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
```
**说明**
- 在第一个测试用例中，我们可以将下标从 3 到 6 的子数组旋转 2 次（即选择 $ l = 3 $, $ r = 6 $ 和 $ k = 2 $）以得到最优数组：$$
[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}]
$$ 因此答案是 $ a_n - a_1 = 11 - 1 = 10 $。
- 在第二个测试用例中，最优的做法是旋转下标从 1 到 1 的子数组 2 次。
- 在第四个测试用例中，最优的做法是旋转下标从 1 到 4 的子数组 3 次。所以答案是 $ 8 - 1 = 7 $。**题目大意** 给定一个长度为 $ n $ 的数组 $ a $，可以选定**一个**区间 $[l, r]$ 进行**恰好一次**操作，求操作后最大的 $ a_n - a_1 $。 操作方法：选定区间 $[l, r]$ 和旋转次数 $ k $，每次旋转为 $ a_l = a_{l + 1}, a_{l + 1} = a_{l + 2}, \ldots, 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 $。 **题目描述** Mainak 拥有一个由 $ n $ 个正整数组成的数组 $ a_1, a_2, \ldots, a_n $。他将对此数组执行一次以下操作： - 选择数组的一个子段并循环旋转任意次数。 形式上，他可以执行以下操作恰好一次： - 选择两个整数 $ l $ 和 $ r $，使得 $ 1 \le l \le r \le n $，以及任意正整数 $ k $。 - 重复此操作 $ k $ 次：设置 $ a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l $（所有更改同时发生）。 Mainak 想要通过恰好一次这样的操作来最大化 $ (a_n - a_1) $ 的值。确定他可以获得的最大 $ (a_n - a_1) $ 值。 **输入输出格式** **输入格式** - 每个测试包含多个测试用例。第一行包含一个整数 $ t \; (1 \le t \le 50) $ —— 测试用例的数量。测试用例的描述如下。 - 每个测试用例的第一行包含一个整数 $ n \; (1 \le n \le 2000) $。 - 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n \; (1 \le a_i \le 999) $。 - 保证所有测试用例的 $ n $ 之和不超过 $ 2000 $。 **输出格式** - 对于每个测试用例，输出一个整数 —— Mainak 通过恰好一次操作可以获得的最大 $ (a_n - a_1) $ 值。 **输入输出样例** **输入样例 #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 ``` **说明** - 在第一个测试用例中，我们可以将下标从 3 到 6 的子数组旋转 2 次（即选择 $ l = 3 $, $ r = 6 $ 和 $ k = 2 $）以得到最优数组：$$ [1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}] $$ 因此答案是 $ a_n - a_1 = 11 - 1 = 10 $。 - 在第二个测试用例中，最优的做法是旋转下标从 1 到 1 的子数组 2 次。 - 在第四个测试用例中，最优的做法是旋转下标从 1 到 4 的子数组 3 次。所以答案是 $ 8 - 1 = 7 $。