【普及】最大环形子数组和

给你一个长度为 $n$ 的 环形 整数数组 $a$ ，请你找出一个具有 最大和 的连续子数组（子数组最少包含一个元素），返回其 最大和

子数组 是数组中的一个连续部分。

环形数组：意味着数组的末端将会与开头相连呈环状。形式上，$a[i]$ 的下一个元素是 $a[(i + 1)$，$a[i]$ 的前一个元素是 $a[(i - 1 + n)$

输入格式

第一行一个整数 $n$，表示数的个数，($1 \le n \le 10^5$)

第二行有 $n$ 个整数，$a_i$ 表示第 $i$ 个数 ($-10^4 \le a_i \le 10^4$)。

输出格式

对于每组数据输出一行，包含答案

4
1 -2 3 -2

3

3
5 -3 5

10

3
-3 -2 -3

-2

提示

【样例 1 解释】

• 子数组 $[3]$ 有最大和 $3$

【样例 2 解释】

• 子数组 $[5, 5]$ 有最大和 $10$

【样例 3 解释】

• 子数组 $[-2]$ 有最大和 $-2$

【数据范围】

• $1 \le n \le 10^5$
• $-10^4 \le a_i \le 10^4$
• 题目保证答案在 int 范围内

来源

• 参考答案