009Maximum Subarray

Problem

给定一个整数数组 nums。

请你找到一个具有最大和的连续子数组，返回这个最大和。

子数组中的元素必须在原数组中连续出现，至少包含一个元素。

Examples

示例 1

Input:  nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

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

示例 2

Input:  nums = [1]
Output: 1

示例 3

Input:  nums = [5,4,-1,7,8]
Output: 23

解释：整个数组本身就是最大连续子数组。

Constraints

• $1 \leq$ nums.length $\leq 10^5$
• $-10^4 \leq$ nums[i] $\leq 10^4$