1137: 环形整数串的最大连续和子串
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：85
解决：22
题目描述
你知道最大和子串问题么？就是给你一个整数串，要你求出其中的一个连续子串，要求其和最大。
比如：下面这个长度为6的整数串：-2，2，0，1，-48，1，显然其最大和连续子串是：2，0，1，其和是3。
现的问题是如果求环形整数串的最大连续和子串呢？请编写一个程序解决这个问题。
比如：下面这个长度为6的整数串：-2，2，0，1，-48，1，显然其最大和连续子串是：2，0，1，其和是3。
现的问题是如果求环形整数串的最大连续和子串呢？请编写一个程序解决这个问题。
输入
第一行一个整数n, (1<=n<=1000000)。
第2行有n个整数，都在[-100,100]的范围内，两两之间用一个空格隔开。
第2行有n个整数，都在[-100,100]的范围内，两两之间用一个空格隔开。
输出
仅一个整数，表示环形整数串最大连续子串和。
样例输入 复制
6
-2 3 0 1 -48 80
样例输出 复制
82提示
输入样例
2
1 3
输出样例
4
数据限制
保证50%数据的n<=100
保证70%数据的n<=2000
保证100%数据的n<=1000000
2
1 3
输出样例
4
数据限制
保证50%数据的n<=100
保证70%数据的n<=2000
保证100%数据的n<=1000000