题解

最大子数组和

题目：点我直达

// maxSubArray 最大子数组和
// 这里采用动态规划思路求解
// 定义 dp[i] 为第i个元素的包含前n个子数组的最大值

// 如果 dp[i-1] 为负数的话，就会对当前的dp[i]最大值起到副作用
// 所以我们直接拿arr[i]作为当前dp[i]的最大值即可

// 如果 dp[i-1] 为正数的话，我们直接拿当前的arr[i]加上就是dp[i].因为arr[i]是必须的
// 故不论 arr[i] 是正数还是负数都会产生正作用

// 其中 dp[0] 直接拿 arr[0] 即可

// 动态方程式为: 
//          arr[i]  dp[i-1]<=0
// dp[i] =  
//          arr[i] + dp[i-1] dp[i-1]>0
func maxSubArray(nums []int) int {
    // 定义dp
    var dp = make([]int, len(nums))
	
    // dp[0] 没法按照下面的公式求解
    dp[0] = nums[0]
    for i, num:= range nums{
        if i == 0{
            continue
        }
        // 下面就是转移方程式
        if dp[i-1] <=0 {
            dp[i] = num
        }else{
            dp[i] = num + dp[i-1]
        }
    }
    // 拿到最大值返回即可
    var m = dp[0]
    for _, d := range dp {
        m = max(d,m)
    }
    return m
}

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