最大子数组和

题目描述

给定一个整数数组，找出其中和最大的连续子数组（子数组至少包含一个元素），并返回该最大和。

子数组是指数组中连续的一段元素。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示数组长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^4 \leq a_i \leq 10^4$），表示数组元素。

输出格式

输出一个整数，表示具有最大和的连续子数组的和。

示例

示例 1

输入：

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

输出：

6

解释：
连续子数组 [4, -1, 2, 1] 的和为 $4 + (-1) + 2 + 1 = 6$，是所有连续子数组中和最大的。

示例 2

输入：

1
1

输出：

1

示例 3

输入：

5
5 4 -1 7 8

输出：

23

解释：
整个数组的和为 $5 + 4 + (-1) + 7 + 8 = 23$，即最大子数组和。

数据范围

• $1 \leq n \leq 10^5$
• $-10^4 \leq a_i \leq 10^4$