题目描述

给定 $n$ 个整数（可能为负数）组成的序列 $\{a_1,\ a_2,\ \dots,\ a_n\}$ ，其任意连续的子段可以表示为 $\{a_i,\ a_{i+1},\ \dots,\ a_{j-1},\ a_j\}$，其中 $1\leq i \leq j \leq n$。

最大子段就是选出所有连续且非空的一段中元素之和最大的一个。

依此定义，所求的最优值为： $\text{Max}\{\ a_i+a_{i+1}+\dots+a_{j-1}+a_j\}$。

例如给定序列 $\{-2, 11, -4, 13, -5, -2\}$，其最大连续子段为 $\{11,-4,13 \}$，最大和为 $20$。

输入格式

第一行一个整数 $n$；

第二行有 $n$ 个整数 $a_i$，每个整数之间有一个空格。

输出格式

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

6
-2 11 -4 13 -5 -2

20

3
-1 -5 -2

-1

数据范围

对于 $100\%$ 的数据： $1\leq n\leq 2 \times 10^6$，$0\leq |a_i|\leq 3\times 10^9$。