输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
第一行:正整数n
第二行:n个整数
最大子数组和
输入:
9 -2 1 -3 4 -1 2 1 -5 4
输出:
6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
1 <= n <= 10000
-100 <= 每个数组元素 <= 100