题目描述

给出一个长度为n的序列a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行一个正整数n(1≤n≤2×10^5)；

第二行n个整数ai(-10^4≤ai≤10^4)。

输出格式

一个整数表示最大子段的和。

输入/输出样例

7
2 -4 3 -1 2 -4 3

4

样例解释

选取[3,5]子段{3, -1,2}，其和为4。

说明/提示

时间1000ms，内存256MiB