U593332 环上最大子段和
题目描述
给定一个长度为 $n$ 的环状数组 $a$ ，$a_i \ (1 \le i \le n)$ 可正可负。求出环上连续一段数字的和，可以为空段。
输入格式
输入共两行。
第一行包含整数 $n$ ，表示数组长度。
接下来一行 $n$ 个整数 $a_i \ (1 \le i \le n)$ 。
输出格式
输出共一行
第一行包含一个非负整数，表示答案。
说明/提示
对于 $24 \%$ 的数据，$1 \le n \le 10^4 , |a_i| \le 100$ 。
对于另外 $12 \%$ 的数据，$a_i \ge 0$ 。
对于 $100 \%$ 的数据，$1\le n \le 5 \times 10^6 , |a_i| \le 10^9$ 。