题目描述

有 N 个数，要你从中找出一段连续的一段（在术语上，这连续一段称为这 N 个数的子段），使得这个子段的和最大。

补充说明： 如果每个数都是非负数，那么最大子段和一定就是 N 个数全部相加（N 个数本身也是自己的子段，这是一种特殊情况）。当前问题之所以是难题，是因为这 N 个数里面有负数，把全部数加起来未必能使得和最大。

输入格式
第一行 1 个正整数：N。
第二行 N 个 正整数 $a_i$

数据范围
1 <= N <= 100000
-10000 <= $a_i$ <= 10000

输出格式
一个整数，长度为 k 的最大子段和。

样例

6
-1 2 -3 3 4 -10

7