题目描述

给定一个环状数组，数组中的每个位置上有一个整数（可以为正、负或零）。在这个环状数组中，你可以选择连续的一段数字（可以是空段，此时和为 0），求这段数字和的最大可能值。

序列长度 $n \le 2 \times 10^5$，序列中的元素的绝对值不超过 $10^9$。

输入格式

第一行一个正整数 $n$，表示数组的长度。

第二行 $n$ 个整数，依次表示环上每个位置的数字。

输出格式

一行一个整数，表示最大子段和（空段的和为 $0$）。

5
2 -4 1 3 -2

4

样例1说明：

（可以选取子段 $1,3$，和为 $4$；或者选取跨环的子段 $3,-2,2$，和也为 $3$，不够最优。实际上不跨环的最大子段和为 $1+3=4$，跨环的最大子段和为总和减去最小子段和：总和 $0$，最小子段和 $-4$，$0-(-4)=4$，最大为 $4$）

3
-1 -2 -3

0

说明/提示

• 对于 $30\%$ 的数据，$n \le 100$。
• 对于 $70\%$ 的数据，$n \le 10^4$。
• 对于 $100\%$ 的数据，$n \le 2\times 10^5$，序列中数字的绝对值不超过 $10^9$。

题目改编自《深入浅出-进阶篇》例 15-6。