动态规划之最大子序和（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)