j02082. 环形最大子段和 未做

$n$ 个整数围成一个环。选一段非空且长度不超过 $n$ 的连续弧（可从任意位置出发、可绕过接头），使弧上数字之和最大。求这个最大和。

第一行一个整数 $n$；第二行 $n$ 个整数。

一行一个整数，表示最大和。

• 对于 30% 的数据，$n$ $\le$ $1\times 10^3$（枚举起点走一圈 $O(n^2)$ 可过）。
• 对于 60% 的数据，$n$ $\le$ $5\times 10^3$。
• 对于 100% 的数据，$1\le n\le 2\times 10^5$，$|a_i|\le 10^9$。