翻转
题号:NC205995
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

由于牛牛非常懒,所以它直接告诉你要完成的第二个任务:

给出一个环,强制要求使用你的神力将这个环的某个区间翻转一次。

问非空子段的和最大是多少。

输入描述:

第一行一个数n

第二行n个数,表示一个首尾相接的环

输出描述:

强制翻转一个区间后的非空子段的和最大值
示例1

输入

复制
5
1 2 3 4 5

输出

复制
15
示例2

输入

复制
6 
3 2 -1 1 -1 5

输出

复制
11

备注:

对于55%的数据,1 <= n <= 400

对于80%的数据,1 <= n <= 5000

对于100%的数据,1 <= n <= 200000 , -1e9 <= a[i] <= 1e9