501 - 最大子段和
时间限制 : 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。