题解链接

LeetCode 53. 最大子数组和

题目描述

给定一个长度为 $n$ 的整数数组 $nums$，请你找出一个具有最大和的连续子数组。

子数组最少包含一个元素。

请返回该连续子数组的最大和。

子数组是数组中的一个连续部分。

输入描述

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

第二行输入 $n$ 个整数，表示数组 $nums$ 中的元素。

输出描述

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

样例 $1$

输入

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

输出

6

样例解释

连续子数组 $[4, -1, 2, 1]$ 的和最大，为 $6$。

样例 $2$

输入

1
1

输出

1

样例 $3$

输入

5
5 4 -1 7 8

输出

23

数据范围

$1 <= n <= 10^5$

$-10^4 <= nums[i] <= 10^4$