1326 - 最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

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

输入

第一行为整数n,表示有数组有n个元素

第二行为n个整数,表示数组元素的值

输出

最大子数组和

样例

输入

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

输出

6

输入

1
1

输出

1

输入

5
5 4 -1 7 8

输出

23

提示

1 <= nums.length <= 10^5

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

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题