题目描述

输入 $n$（$1 \le n \le 1000$）及 $n$ 个整数（绝对值 $\le 10^5$），求出数组中连续一段数字的最大和。允许段长度为 1，保证至少有一个正数。

输入格式

第一行：整数 $n$
第二行：$n$ 个整数，空格分隔。

输出格式

输出一个整数，表示最大连续子段和。

样例

6
-2 3 -1 2 -1 4

7

（最大子段为 3 -1 2 -1 4，和为 7）

4
1 2 3 4

10