8367: DP9 环形数组的连续子数组最大和
[Creator : ]
Description
给定一个长度为 n 的环形整数数组，请你求出该数组的 非空 连续子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。例如，对于数组 [1,3,-5,2,-4] 而言，第一个数 1 的前一个数是最后一个数 -4。
环形数组 意味着数组的末端将会与开头相连呈环状。例如，对于数组 [1,3,-5,2,-4] 而言，第一个数 1 的前一个数是最后一个数 -4。
Input
第一行输入一个正整数 n ，代表数组的长度。
第二行为 n 个整数 $a_i$，每个整数之间用空格隔开，代表数组的各个元素。
第二行为 n 个整数 $a_i$，每个整数之间用空格隔开，代表数组的各个元素。
Output
输出一个整数，为原数组的非空子数组的最大可能和。
Constraints
$1≤n≤1∗10^5$
$-10^4≤a_i≤10^4$
$-10^4≤a_i≤10^4$
Sample 1 Input
3
5 -3 5
Sample 1 Output
10
从子数组 [5,5] 得到最大和 5 + 5 = 10
Sample 2 Input
4
3 -2 2 -3
Sample 2 Output
3
从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3