序列最大连续和

题目描述

Y 同学最近在研究序列的性质。他得到了一个长度为 $N$ 的整数序列 $A = \{A_1, A_2, \dots, A_N\}$。

Y 同学定义一个区间的“连续和”为该区间内所有元素的累加和。具体而言，对于一段连续的区间 $[l, r]$（$1 \le l \le r \le N$），其和为：

Y 同学希望从中选取一段非空的连续区间，使得该区间的连续和最大。请你编写一个程序，帮助他计算出这个最大的和。

输入格式

第一行包含一个正整数 $N$，表示序列中元素的个数。 第二行包含 $N$ 个整数，依次表示 $A_1, A_2, \dots, A_N$，相邻两个整数之间用一个空格隔开。

输出格式

输出一行一个整数，表示该序列中非空连续区间的最大和。

样例

样例输入 #1

7
2 -4 3 -1 2 -3 4

样例输出 #1

5

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 10^6$，$\vert A_i \vert \le 10^9$。

特殊性质 A：保证对于所有的 $1 \le i \le N$，均有 $A_i > 0$。 特殊性质 B：保证对于所有的 $1 \le i \le N$，均有 $A_i \le 0$。