问题 H: 大嘴猫吃金币

问题 H: 大嘴猫吃金币

时间限制: 1 Sec  内存限制: 128 MB
提交: 1207  解决: 283
[状态] [讨论版] [提交] [命题人:]
题目描述

  地面上有排成一条直线的n个金币,金币有不同的价值(甚至是负的),大嘴猫想用它的大嘴来吃这些金币。但是大嘴猫只能张一次嘴,所以它只能吃连续一段的金币。你知道大嘴猫最多能吃多大价值的金币吗?


输入

第一行一个整数n,表示有n个金币 。1 <= n <= 1000000。

接下来n行每行一个整数x,表示金币的价值。x在int范围内。

输出

一行一个整数,表示最多吃下金币的价值。

样例输入 Copy
4
1 2 -1 10
样例输出 Copy
12