题目描述

给出数组 $a$ 的元素 $a_1,a_2,\ldots,a_n$ 的值。如果取连续且非空的一段，那么这一段的元素和最大是多少？

输入格式

第一行，一个正整数 $n$，表示数组 $a$ 的长度。

第二行，$n$ 个用空格隔开的整数，依次为 $a_1,a_2,\ldots,a_n$。

输出格式

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

输入输出样例

输入 #1

6
1 -6 5 -4 2 4

输出 #1

7

说明/提示

选择连续子段 $5,-4,2,4$，可以得到最大和 $7$。

数据范围

• 对于 $60\%$ 的数据，$n\le 100$；
• 对于 $80\%$ 的数据，$n\le 5000$；
• 对于全部数据，$n\le 100000$，$-10000\le a_i\le 10000$。

数组 $a$ 中至少有一个正数。

6
1 -6 5 -4 2 4

7

29
-3519 9284 2490 -7985 -705 -4979 1688 -518 5402 -9716 -6350 9972 174 247 4642 -5053 3642 -2150 -6661 -1583 -7999 -830 -1734 5336 -7671 -4669 7337 6625 -6661

15035

51
1949 704 3022 -2428 -7283 -6946 4389 3589 6898 6699 -3887 -30 6357 -5332 -2734 -4355 -2033 4981 -8739 7687 5897 5908 7803 -2344 -1070 -5684 147 -5423 -9844 1253 -2458 -2407 -7682 1942 9358 1937 -3085 7519 3615 2331 -9143 -3633 2934 9313 3866 7054 2204 -242 789 -5934 7027

37852