该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

给出一个整数序列，问最大子段和。

[2,-1,3,-5,3]的最大子段和是2-1+3=4。

子段是连续增长的一段连续的序列，不间断。比如：2、3、3不是最大子段。

要求写一个O(n)的算法。

输入描述

第一行，一个整数n，表示序列的长度

第二行n个整数，每个整数以空格隔开，分别是a1 a2 a3......an-1 an

【输入样例】

6
-2 11 -4 13 -5 -2

【输出样例】

20

提示

数据范围

10<=n<=10000

-1000<=ai<=1000