题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

golang 代码

func maxSubArray(nums []int) int {
    sum := 0
    big := nums[0]
    for _,num := range nums {
        if sum >= 0 {
            sum += num
        }else{
            sum = num
        }
        if sum > big {
            big = sum
        }
    }
    return big
}