动态规划之最大子序和(53)

题目说明

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

示例:

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

进阶:

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

题目链接:53. 最大子序和

动态规划分析

0. 如何识别使用动态规划解题

题目求最大和,属于求最值、最优解的问题。

1-2. 定义状态及状态转移方程

按照常规的动态规划思路,一般是这样定义状态 dp[i] 的:

dp[i] = nums[0...i] 中的「最大的子数组和」

按照这个定义,无法由 dp[i] 推导 dp[i+1],因为题目求的最大和的子数组是连续的,而状态描述的是 nums[0...i] 中的「最大的子数组和」,因此要重新定义状态:

dp[i] = 以 nums[i] 为结尾的「最大的子数组和」

使用数学归纳法来找状态转移方程:假设已经算出 dp[i-1] ,如何推导出 dp[i] 呢?

当子数组遇到数字 nums[i] 时,有两种选择:要么把 nums[i] 合并到子数组中;要么把 nums[i] 作为新的子数组;求这两种选择中的最大值,即为 dp[i] ,因此得到状态转移方程:

dp[i] = max(dp[i-1] + nums[i], nums[i])

3. 状态初始化

  • 当 nums 为空时,返回0。
  • 当 nums 只有一个元素时,返回 nums[0]

即 dp[0] = nums[0]。

4. 结果输出

这里的结果输出不再是常规的 dp[n] 了,而是在遍历过程中找到最大值。

5. 空间优化

通过状态转移方程可知,dp[i] 只与前一个状态 dp[i-1] 有关,可以进行状态压缩,降低空间复杂度为 O(1) 。

代码实现

func maxSubArray(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	pre, m := nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		pre = max(pre+nums[i], nums[i])
		if pre > m {
			m = pre
		}
	}

	return m
}

func max(x int, y int) int {
	if x > y {
		return x
	}
	return y
}
  • 时间复杂度:O(n),遍历一次数组。
  • 空间复杂度:O(1)
上一篇:剑指 Offer 53 - I. 在排序数组中查找数字 I


下一篇:剑指 Offer 53 - I. 在排序数组中查找数字 I