题解 | #连续子数组的最大和#

//动态规划，最大子序和，时空都是On
package main

func FindGreatestSumOfSubArray( array []int ) int {
    if len(array) == 0 {
        return 0
    }
    
    n := len(array)
    res := array[0]
    
    dp := make([]int, n+1)
    dp[0] = array[0]
    
    for i := 1; i < n; i++ {
        dp[i] = max(dp[i-1] + array[i], array[i])
        res = max(res, dp[i])
    }
    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}