DP 第二讲 - 最大子序和

在上一篇文章011.动态规划系列 —第一讲(70)中，我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中，我们将继续通过1道简单题型，进一步学习动态规划的思想。

01、题目分析

第53题：最大子序和

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

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

拿到题目请不要直接看下方题解，先自行思考2-3分钟….

02、题目图解

首先我们分析题目，一个连续子数组一定要以一个数作为结尾 ，那么我们可以将状态定义成如下：

dp[i]：表示以 nums[i] 结尾的连续子数组的最大和。

那么为什么这么定义呢？因为这样定义其实是最容易想到的！在上一节中我们提到，状态转移方程其实是通过1-3个参数的方程来描述小规模问题和大规模问题间的关系。 当然，如果你没有想到，其实也非常正常！因为该问题最早于 1977 年提出，但是直到 1984 年才被发现了线性时间的最优解法。 根据状态的定义，我们继续进行分析：如果要得到 dp[i]，那么 nums[i] 一定会被选取。并且 dp[i] 所表示的连续子序列与 dp[i-1] 所表示的连续子序列很可能就差一个 nums[i] 。即：

dp[i] = dp[i-1]+nums[i] , if (dp[i-1] >= 0)

但是这里我们遇到一个问题，很有可能 dp[i-1] 本身是一个负数 。那这种情况的话，如果 dp[i] 通过 dp[i-1]+nums[i] 来推导，那么结果其实反而变小了 ，因为我们 dp[i] 要求的是最大和。所以在这种情况下，如果 dp[i-1] < 0，那么 dp[i] 其实就是 nums[i] 的值。即

dp[i] = nums[i] , if (dp[i-1] < 0)

综上分析，我们可以得到：

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

得到了状态转移方程，但是我们还需要通过一个已有的状态的进行推导，我们可以想到 dp[0] 一定是以 nums[0] 进行结尾 ，所以

dp[i] = dp[i-1]+nums[i] , if (dp[i-1] >= 0) dp[0] = nums[0]

在很多题目中，因为 dp[i] 本身就定义成了题目中的问题，所以 dp[i] 最终就是要的答案 。但是这里状态中的定义，并不是题目中要的问题，不能直接返回最后的一个状态 (这一步经常有初学者会摔跟头) 。所以最终的答案，其实我们是寻找：

max(dp[0], dp[1], …, d[i-1], dp[i])

分析完毕，我们绘制成图（图中假定 nums 为 [-2,1,-3,4,-1,2,1,-5,4]）： PNG

03、Go语言示例

根据以上分析，可以得到代码如下：

  1.   1. //Go
  2.     2. func maxSubArray(nums []int) int {
  3.     3.     if len(nums) < 1 {
  4.     4.         return 0
  5.     5.     }
  6.     6.     dp := make([]int, len(nums))
  7.     7.     //设置初始化值 
  8.     8.     dp[0] = nums[0]
  9.     9.     for i := 1; i < len(nums); i++ {
  10.     10.         //处理 dp[i-1] < 0 的情况
  11.     11.         if dp[i-1] < 0 {
  12.     12.             dp[i] = nums[i]
  13.     13.         } else {
  14.     14.             dp[i] = dp[i-1] + nums[i]
  15.     15.         }
  16.     16.     }
  17.     17.     result := -1 << 31
  18.     18.     for _, k := range dp {
  19.     19.         result = max(result, k)
  20.     20.     }
  21.     21.     return result
  22.     22. }
  23.     23.   24. func max(a, b int) int {
  24.     25.     if a > b {
  25.     26.         return a
  26.     27.     }
  27.     28.     return b
  28.     29. }

我们可以进一步精简代码为：

  1.   1. //Go
  2.     2. func maxSubArray(nums []int) int {
  3.     3.     if len(nums) < 1 {
  4.     4.         return 0
  5.     5.     }
  6.     6.     dp := make([]int, len(nums))
  7.     7.     result := nums[0]
  8.     8.     dp[0] = nums[0]
  9.     9.     for i := 1; i < len(nums); i++ {
  10.     10.         dp[i] = max(dp[i-1]+nums[i], nums[i])
  11.     11.         result = max(dp[i], result)
  12.     12.     }
  13.     13.     return result
  14.     14. }
  15.     15.   16. func max(a, b int) int {
  16.     17.     if a > b {
  17.     18.         return a
  18.     19.     }
  19.     20.     return b
  20.     21. }

复杂度分析：时间复杂度：O(N)。空间复杂度：O(N)

整理人：豆包AI助手