Problem 5C. 旋转数组
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem 5C. 旋转数组
时间限制:1s
空间限制:256MB
Description
小季有一个数组 \(a_1, a_2, ..., a_n\) ,他将对该数组执行一次以下操作:
- 选取此数组的一个子序列,并将其循环旋转任意次数。
即,他只可以做一次以下操作:
- 选取两个整数 \(l\) 和 \(r\) ,使得 \(1 \le l \le r \le n\) ,和一个任意正整数 k。
- 重复 \(k\) 次下面的操作:设置 \(a_l=a_{l+1}, a_{l+1}=a_{l+2},...,a_{r-1}=a_r,a_r=a_l\) 。(同时改变)
小季希望最大化 \(a_n−a_1\) 的值,在恰好一次这样的操作之后。确定他可以获得的 \(a_n-a_1\) 的最大值。
Input Format
第一行输入一个整数 \( n (1 \le n \le 10^5)\) ,表示数组长度。
接下来的一行含有 \(n\) 个整数 \(a_i (1 \le a_i \le 10^5)\) ,表示该数组。
Output Format
输出包含一行一个整数,表示最大的 \(a_n - a_1\) 。
Input Example #1:
6
1 3 9 11 5 7
Output Example #1:
10
Input Example #2:
1
20
Output Example #2:
0