题目描述

给定一个长度为 $n$ 的整数序列 $a$，从中选出一段连续且非空的子段，使得子段的元素之和最大。输出这个最大和。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

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

样例

7
2 -4 3 -1 2 -4 3

4

提示

样例解释

选取第 $3$ 到第 $5$ 个元素 $\{3,-1,2\}$，和为 $4$。

数据范围

• 对于 $40\%$ 的数据，$n \le 2 \times 10^3$。
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$-10^4 \le a_i \le 10^4$。