3120 - 环形取数
题目描述
给定 N 个整数 A_1,A_2,\dots,A_n，这 N 个整数首尾相连构成一个圆环，请从圆环中取出一段连续的数字（至少取 1 个），使得该段连续数字之和最大。
请输出最大的数字和。
输入
第 1 行输入整数 N。
第 2 行输入 N 个整数，数字之间用空格隔开。
输出
输出从圆环中取出连续数字的最大和。
样例
输入
5 -11 7 -3 11 -17
输出
15
输入
8 16 13 15 -30 -9 20 17 -1
输出
80
输入
10 15 19 4 8 -7 15 -14 -10 8 5
输出
67
说明
样例 1 解释
选择区间 7、-3、11 这几个连续的数，求和为 15。
样例 2 解释
由于首尾相连构成圆环，因此从圆环上选择如下几个连续的数 20、17、-1、16、13、15，求和为 80。
数据范围
对于 40\% 的数据，1 \le N \le 1000。
对于 100\% 的数据，1 \le N \le 10^5，-10^4 \le A_i \le 10^4。
标签
