1049: 最大连续子序列和

Memory Limit:128 MB Time Limit:0.500 S Judge Style:Text Compare Creator:
Submit:691 Solved:167

Description

给定一个数列,其中可能有正数也可能有负数,我们的任务是找出其中连续的一个子数列(允许空序列,空序列的和为0),使它们的和尽可能大。我们一起用多种方式,逐步优化解决这个问题。



数据范围 0 < n <= 100000

不允许普通用户打印题目,请教师登录后使用。如有疑问请联系管理员!

Input

第一行一个数n,表示数列的长度

接下来n行,每行一个数,表示数列的具体数值

Output

一个数,最大连续子序列和

Sample Input Copy

8
-1
7
-1
0
4
-7
2
3

Sample Output Copy

10