描述

求一个序列的最大子段和即最大连续子序列之和。例如序列[4, -3, 5, -2, -1, 2, 6, -2]的最大子段和为11=[4+(-3)+5+(-2)+(-1)+(2)+(6)]。

格式

输入格式

第一行一个数表示有n个数
一串共n个数，以空格隔开

输出格式

一个数表示最大子段和

样例1

样例输入1

6
-2   11  -4  13  -5  -2

样例输出1

20

限制

各个测试点1s，16MiB内存空间。