剑指 Offer 42. 连续子数组的最大和

题目

剑指 Offer 42. 连续子数组的最大和

题解

暴力求解

func maxSubArray(nums []int) int {
    //一个临时值，和一个最大值
    temp,max := 0,nums[0]
    for i:=0;i<len(nums);i++ {
        if (temp + nums[i]) > nums[i] {
            temp = temp + nums[i]
        } else {
            temp = nums[i]
        }
        if temp > max {
            max = temp
        }
    }

    return max  //返回最大值
}

动态规划（DP）

//Go
func maxSubArray(nums []int) int {
	// 因为后面会使用到 nums 的长度
	// 所以先进行判空操作
	// 如果数组 nums 为空，返回 0
	if len(nums) == 0 {
		return 0
	}
	// 获取数组的长度
	n := len(nums)
	// 设置一个数组 dp，长度和数组 nums 长度一致
	// dp[0] 表示以第 0 个元素结尾的最大子数组的和
	// dp[1] 表示以第 1 个元素结尾的最大子数组的和
	// dp[i] 表示以第 i 个元素结尾的最大子数组的和
	dp := make([]int, n)
	// dp[0] 表示以第 0 个元素结尾的最大子数组的和
	// 初始化 dp[0]
	dp[0] = nums[0]

	// 变量 maxNum 表示数组 dp 中最大的那个值
	// 即 maxNum 表示最大的连续字段和
	maxNum := dp[0]

	// 从 1 开始遍历数组 nums
	for i := 1; i < n; i++ {
		// 在遍历的过程中，去获取以第 i 个元素结尾的最大子数组的和
		// 如果以 nums[i-1]结尾的最大字段和为正数
		// 那么以第 i 个元素结尾的最大子数组的和就是自己本身加上以 nums[i-1]结尾的最大字段和
		if dp[i-1] > 0 {
			// dp[i-1] 是正数
			// 所以 dp[i] 的值为 nums[i] 加上 dp[i-1]
			// 因为 正数 + 变量 > 变量
			// dp[i -1] + nums[i] > nums[i]
			dp[i] = dp[i-1] + nums[i]
		} else {
			// 否则 dp[i-1] 不是正数，为负数或者 0
			// 那么 dp[i] 的值为 nums[i]
			// 因为 负数 + 变量 < 变量
			// dp[i -1] + nums[i] < nums[i]
			dp[i] = nums[i]
		}
		// 在更新 dp[i] 的过程中，更新 maxNum 的值
		// 如果此时 dp[i] 的值大于了 maxNum
		if maxNum < dp[i] {
			// 那么 maxNum 更新为 dp[i]
			maxNum = dp[i]
		}
	}

	return maxNum
}