题目描述

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

输入格式

第一行输入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$,答案在 long int 范围内。