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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型
*/
func FindGreatestSumOfSubArray( array []int ) int {
    // write code here
    // 直接动态规划
    // dp[i] 代表到达当前下标的子数组最大和
    // dp[0] = array[0]
	// 递推表达式：判断是和之前子数组组合在一起的和更大，还是当前元素自己组成子数组更大
  	// -1 -1 2 对于第三个元素来说，它的最大子数组肯定是不需要前面那部分子数组的
  	// 1 1 2 对于第三个元素来说，它的最大子数组肯定是需要包含前面大部分子数组的
    // dp[i] = max(dp[i-1]+array[i], array[i])
    if len(array) == 0 {
        return 0
    }

    dp := make([]int, len(array))
    dp[0] = array[0]
    ans := dp[0]

    for i := 1; i < len(array); i++ {
        dp[i] = max(dp[i-1]+array[i], array[i])
        if dp[i] > ans {
            ans = dp[i]
        }
    }

    return ans  
}

func max(a, b int) int {
    if a < b {
        return b
    }

    return a
}