1432: 最大子序列和*

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：95 Solved：30

Description

给一个整数序列（可以正可以负），找出和最大的子序列。

子序列是指在一个序列当中选取一段连续的元素组成新序列。例如，序列[4,5,6]是序列[1,2,3,4,5,6,7,8,9,10]的一个子序列。





Input

输入两行
第一行是一个整数n，表示序列长度。
第二行是n个整数。

Output

输出所有子序列之和的最大值。

Sample Input Copy 

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output Copy 

10

HINT

1<=n<=100000
每个数字范围为[-10000,10000]。
任意子序列和的范围不超过int表达的范围。