连续子数组的最大和.

输入一个整型数组,数组里有整数也有负数。
数组中一二或连续的多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if array == None or len(array) <= 0:
            return 0

        ncursum = 0
        nGreaterSum = array[0]

        for i in range(len(array)):
            if ncursum <= 0:
                ncursum = array[i]
            else:
                ncursum += array[i]

            if ncursum > nGreaterSum:
                nGreaterSum = ncursum
        return nGreaterSum


    def FindGreatestSumOfSubArray(self, array):
        if array == None or len(array) <= 0:
            return 0

        alist = [8] * len(array)
        for i in range(len(array)):
            if i == 0 or alist[i-1] <= 0:
                alist[i] = array[i]
            else:
                alist[i] = alist[i-1] + array[i]
        return max(alist)

package main


func MaxList(nums []int) int {
    if len(nums) == 0 {return 0}
    dp := make([]int, len(nums))

    dp[0] = nums[0]
    res := nums[0]

    for i:=1; i<len(nums); i++ {
        if dp[i-1] > 0 {
            dp[i] = dp[i-1] + nums[i]
        } else {
            dp[i] = nums[i]
        }

        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}


func MaxList2(nums []int) int {
    if len(nums) == 0 {return 0}

    dp := make([]int, len(nums))
    copy(dp, nums)
    max := dp[0]
    for i := 1; i<len(nums); i++ {
        if dp[i-1]>0 {
            dp[i] = dp[i-1] + dp[i]
        }
        if dp[i] > max {
            max = dp[i]
        }
    }
}