最大子数组和（Maximum Subarray）

题目描述

给定一个整数数组 nums，请找出 ​具有最大和的连续子数组​（子数组最少包含一个元素），并返回其最大和。

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

输入格式

第一行输入一个整数 n，表示数组长度。

第二行输入 n 个整数，表示数组 nums。

输出格式

输出一个整数，表示 ​最大子数组的和​。

样例 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

说明

最大子数组为 [1]。

样例 3

输入

5
5 4 -1 7 8

输出

23

说明

最大子数组为：

[5, 4, -1, 7, 8]

其和为：

5 + 4 - 1 + 7 + 8 = 23

数据范围

1 ≤ n ≤ 10^5
-10^4 ≤ nums[i] ≤ 10^4