#P55071. 最大子段和

最大子段和

题目描述

给出一个长度为n的整数列a,选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数,表示序列的长度n; 第二行有n个整数,第i个整数表示序列的第i个数字aia_i

输出格式

输出一行一个整数表示答案:最大子段和的值。

样例

样例输入

6
-2 11 -4 13 -5 -2

样例输出

20

数据范围与提示

n<=100