题目描述

$N$ 个数围成一圈，要求从中选择若干个连续的数（注意每个数最多只能选一次）加起来，问能形成的最大的和。选择的数的数量不能为 $0$。

输入格式

第一行输入 $N$，表示数字的个数，第二行输入这 $N$ 个数字。

输出格式

输出最大和。

8
2 -4 6 -1 -4 8 -1 3

14

数据范围

$40\%$ 的数据：$1 \le N \le 300$

$60\%$ 的数据：$1 \le N \le 2000$

$100\%$ 的数据：$1 \le N \le 100000$，答案在 int 范围内。

upd $2024.12.7$：新增加两组 hack 数据。