题目描述

给出数组 a 的元素 a[1], a[2], …, a[n] 的值，如果我们取连续且非空的一段，那么这段的和最大是多少？

输入格式

第 1 行，是一个正整数 n，数组 a 的长度。

第 2 行，用空格隔开的 n 个整数，依次是 a[1], a[2], …, a[n] 的值。

输出格式

1 个整数，为所求的最大的和。

输入样例 #1

6
1 -6 5 -4 2 4

输出样例 #1

7

输入样例 #2

5
-61 -86 -51 -46 81

输出样例 #2

81

输入样例 #3

8
-61 -23 0 -34 60 -8 76 38

输出样例 #3

166

提示

取 5, -4, 2, 4 可以得到最大的和 7。

数据范围与约定

对于 60% 的数据，n ≤ 100。

对于 80% 的数据，n ≤ 5000。

对于 100% 的数据，n ≤ 100000；对于 1 ≤ i ≤ n，-10000 ≤ a[i] ≤ 10000。数组 a 中至少有 1 个正数。