501 - 最大子段和

通过次数

74

提交次数

136

时间限制 : 1 秒
内存限制 : 128 MB

给定一整型数列{a1_,a_2...,a_n},找出连续非空子串{a_x,a_{x+1},...,a_y},使得该连续子串的和最大,其中,1<=x<=y<=n

输入

第一行是一个整数n表示序列中共有n个整数,

随后的一行里有n个整数a_i(-100 <= a_i <= 100),表示数列中的所有元素

输出

对于每组测试数据输出和最大的连续子串的和。

样例

输入

5
1 2 -1 3 -2

输出

5

提示

【样例解释】

该数组的最大字段和是前四个元素组成的字段[1,2,-1,3]

【数据规模】

100\%的数据,满足 2≤n≤1000000