1563. [算法课分治] 找到最大子序和

给定一个整数数组 \text{nums},找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

输入

第一行输入一个整数 \text{nums.length} 代表数组的长度

第二行输入一行数字代表数组 \text{nums},数字与数字之间用空格间开

  • 1 \leq \text{nums.length} \leq 3 \times 10^4
  • -100000 \leq \text{nums[i]} \leq 100000

输出

输出一个整数代表子序列最大和

样例

标准输入 复制文本
9
-2 1 -3 4 -1 2 1 -5 4
标准输出 复制文本
6
标准输入 复制文本
1
1
标准输出 复制文本
1
标准输入 复制文本
1
0
标准输出 复制文本
0

提示

第一个样例解释:连续子数组 [4,-1,2,1] 的和最大,为 6

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 2117
通过 1169