AT_donuts_live2014_3 ソーシャルゲーム

为了运营社交游戏，观察每天用户数量的增减是必不可少的。 经营游戏公司的パンチくん想要调查用户数量增加最多的期间，用户数量究竟增加了多少人。 给定每天用户数量的增减数 $a_1,\ a_2,\ …,\ a_N$，请你求出用户数量增减数最大的期间的用户增减数。

输入以如下格式从标准输入给出。 > $N$ $a_1$ $a_2$ ... $a_N$ - 第 $1$ 行给出调查期间的天数 $N\ (1\leq N\leq 100000)$。 - 第 $2$ 行给出调查期间第 $i$ 天的用户增减数 $a_i\ (-1000\leq a_i\leq 1000)$。

请输出用户增减数最大的期间（不少于 $1$ 天）的用户增减数，输出一行，末尾需换行。

## 部分分 对于满足 $1\leq N\leq 3000$ 的测试点，答对可获得 $40$ 分。 ## 样例解释 1 从第 $3$ 天到第 $6$ 天，即 $(2,\ 3,\ -1,\ 2)$ 的增减数之和 $6$ 是最大值。 ## 样例解释 2 整个期间就是用户增减数最大的期间。 ## 样例解释 3 输出有可能为负数。请注意，输出的期间必须不少于 $1$ 天。 由 ChatGPT 4.1 翻译