Problem1501--最大子段和3

1501: 最大子段和3

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 164  Solved: 69
[Submit] [Status] [Web Board] [Creator:]

Description

给出n个整数a_1,a_2,...,a_n,定义b_{i,j}=a_i+a_{i+1}+...+a_j(1\le i\le j\le n),找出所有的b_{i,j}中最大的是多少。

Input

第一行一个整数n(1\le n\le 100000)
第二行n个整数a_1,a_2,...,a_n(-10^9\le a[i]\le 10^9)

Output

输出一行一个整数表示答案。

Sample Input

5
-1 2 3 -4 8

Sample Output

9

Source/Category