环形最大子数组和

题目描述

给定一个整数数组，将其看作首尾相连的环形数组。请找出其中和最大的连续子数组（子数组至少包含一个元素），并返回该最大和。连续子数组可以跨越数组尾部和头部，即可以从某个位置开始，经过数组末尾再回到开头继续选取一段。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示数组长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^4 \leq a_i \leq 10^4$），表示数组元素。

输出格式

输出一个整数，表示环形数组中具有最大和的连续子数组的和。

示例

示例 1

输入：

5
5 -2 3 4 -1

输出：

11

解释：
选择子数组 [3, 4, -1, 5]，跨越了尾部和头部，总和为 $3 + 4 + (-1) + 5 = 11$，为最大值。

示例 2

输入：

4
8 -1 -3 8

输出：

16

解释：
可以选取 [8, 8]（经过尾首相连），总和 $16$。

示例 3

输入：

3
-5 -2 -3

输出：

-2

解释：
全部为负数时，选择单个元素 $-2$ 为最大。

数据范围

• $1 \leq n \leq 10^5$
• $-10^4 \leq a_i \leq 10^4$