最大连续训练收益

题目描述

一名学生连续进行了 $n$ 天训练，第 $i$ 天的训练收益记为 $a_i$。收益可能为正，也可能因为疲劳而为负。现在需要从这 $n$ 天中选择一段连续且非空的训练区间，使这段区间的总收益最大。求这个最大值。

输入格式

第一行输入整数 $n$。第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出最大连续区间和。

样例

6
4 -1 2 1 -8 5

6

说明

选择前四天，收益为 $4-1+2+1=6$。注意：遇到负数并不一定马上舍弃，真正应该舍弃的是“累计收益已经变成负数”的前缀。

数据范围

$1\le n\le 2\times10^5$，$-10^9\le a_i\le 10^9$。答案可能超过 32 位整数范围，请使用 long long。