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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param array int整型一维数组
 * @return int整型一维数组
 */
func FindGreatestSumOfSubArray(array []int) []int {
	// 1. 用一个数组记录以i位置结尾的最大和
	// 		a. i-1 位置是负数 -> arr[i]， 左指针移到当前位置 left = i ,从 i 开始
  			b. i-1 位置是正数 -> arr[i] + dp[i-1] 
	// 2. 每次记录下最大值 和最大区间的下标

	var dp = make([]int, len(array))
	dp[0] = array[0]
	maxsum := dp[0]
	left :=  0 // 子数组开始位置
	resL, resR := 0, 0  // 记录最大区间

	for i := 1; i < len(array); i++ {

        // 判断 i-1 位置是否 < 0
        if dp[i-1] < 0 {
            dp[i] = array[i]
		  	// 新的子数组从 i 位置开始
            left = i
        } else {
            dp[i] = array[i] + dp[i-1]
        }

        if maxsum < dp[i] || maxsum == dp[i] && 
        (resR - resL + 1 ) < (i - left +1 ) {
            maxsum = dp[i]
            resL = left
            resR = i
        }
	}

    var res = make([]int, resR - resL + 1)

    for i := resL; i <= resR; i++ {
        res[i - resL] = array[i]
    }
    
    return res
}