OpenJudge

002:最大子段和

总时间限制:
1000ms
内存限制:
130000kB
描述

给出一段序列A0,A1,A2,A3,A4...,An,选出其中连续且非空的一段使得这段和最大。

如对于一个含有7个整数的序列:2 -4 3 -1 2 -4 3,它的最大子段为4,即选择了3、-1、2这一段。


输入
第一行是一个正整数N,表示了序列的长度。
第2行包含N个绝对值不大于10000的整数A[i],描述了这段序列。

对于40%的数据,有N ≤ 2000。
对于100%的数据,有N ≤ 200000。
输出
包括1个整数,为最大的子段和是多少。
样例输入
7
2 -4 3 -1 2 -4 3
样例输出
4
提示
对于40%的数据,有N ≤ 2000。
对于100%的数据,有N ≤ 200000。
全局题号
16054
添加于
2017-10-04
提交次数
73
尝试人数
31
通过人数
30