g6-07889. 最大子段和 未做

给定长度为 $n$ 的整数数组 $a_1,\dots ,a_n$，选一个非空的连续子段，使它的和最大。求这个最大和。

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$。

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

输入 1

9
-2 1 -3 4 -1 2 1 -5 4

输出 1

6

$1\le n\le 10^5$，$-10^4\le a_i\le 10^4$；答案在 long long 范围内。