题目描述

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

输入格式

第一行是一个整数，表示序列的长度 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案（最大子段和）。

输入样例#1

7
2 -4 3 -1 2 -4 3

输出样例#1

4

题目说明

样例 1 解释：选取子段 $[3,5]$，子段元素为 ${3, -1, 2}$，其和为 $4$。

数据规模与约定：

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