Problem1500--最大子段和2

1500: 最大子段和2

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 111  Solved: 59
[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 1000)
第二行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