看到你这么快地解决了提出的问题,小途非常的着急。
虽然你让他别急,但是他还是很急,因此他给出了一个困难的区间问题。
形式化题意: (max_{l<=i<=r}a_i) \times (r-l+1) - \sum_{l<=i<=r} a_i-(r-l+1) 。求所有非空子区间的最大分值。
第一行一个正整数 n,表示数列的长度。
接下来一行 n 个正整数 a_i ,描述这个数列。
输出一个整数,表示答案。
5 1 2 3 4 5
5
5 1 2 1 2 1
-1
样例解释1
选择 [1,5],分值是 5。
可以证明没有分值更大的区间。
样例解释2
区间的分值可能是负数。
对于 50% 的数据, n≤10^3 。
对于另外 50% 的数据,没有特殊限制。
对于 100% 的数据, 1≤n≤10^6,1≤a i≤10^9 。