leetcode_53. 最大子序和

One minute read
LeetCode
面试 • 算法 • 数据结构

最大子序和

题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/maximum-subarray

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

  1. 遍历更新最大
  2. 动态规划，一维DP

遍历

func maxSubArray(nums []int) int {
    if nums == nil || len(nums) == 0 {
        // errors.New("")
        return 0
    }

    sum, max := nums[0], nums[0]
    for _, v := range nums[1:] { // 注意是从第二个元素开始遍历
        if sum < 0 {
            sum = 0
        }
        sum += v
        if max < sum {
            max = sum
        }
    }
    return max
}
// 执行用时 :8 ms, 在所有 Go 提交中击败了65.46%的用户
// 内存消耗 :3.3 MB, 在所有 Go 提交中击败了65.13%的用户

动态规划

  • 问题拆分

    若第i个数字是最大和连续数组的最右边数字，这就可以分为两种情况：

    • 第i个数字就是最大和连续数组
    • 第i个数字加上0~i-1之间的最大和连续数组是新的最大和连续数组。

最优子结构，就是本次以某个数字结尾的最大序列和的值，

其实是依赖 (上个数字结尾的最大序列和的值+本次结尾的值 ) 和 本次结尾的值 做对比

  • 递推公式 dp[i] = max{nums[i], dp[i-1]+nums[i]}
func maxSubArray(nums []int) int {
	if len(nums) < 1 {
		return 0
	}

	dp := make([]int, len(nums))
	dp[0] = nums[0]
	ret := dp[0]
	for i := 1; i < len(nums); i++ {
		dp[i] = max(nums[i], dp[i-1]+nums[i])
		ret = max(ret, dp[i])
	}
	return ret
}

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

分享：