专栏首页小浩算法《剑指offer》第26天:最大子序和

《剑指offer》第26天:最大子序和

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

01、题目分析

第53题:最大子序和

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [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]):

03、Go语言示例

根据以上分析,可以得到代码如下:

//Go
func maxSubArray(nums []int) int {
 if len(nums) < 1 {
  return 0
 }
 dp := make([]int, len(nums))
    //设置初始化值 
 dp[0] = nums[0]
 for i := 1; i < len(nums); i++ {
        //处理 dp[i-1] < 0 的情况
  if dp[i-1] < 0 {
   dp[i] = nums[i]
  } else {
   dp[i] = dp[i-1] + nums[i]
  }
 }
 result := -1 << 31
 for _, k := range dp {
  result = max(result, k)
 }
 return result
}

func max(a, b int) int {
 if a > b {
  return a
 }
 return b
}

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

//Go
func maxSubArray(nums []int) int {
 if len(nums) < 1 {
  return 0
 }
    dp := make([]int, len(nums))
 result := nums[0]
    dp[0] = nums[0]
 for i := 1; i < len(nums); i++ {
  dp[i] = max(dp[i-1]+nums[i], nums[i])
  result = max(dp[i], result)
 }
 return result
}

func max(a, b int) int {
 if a > b {
  return a
 }
 return b
}

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

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》第28天:最长上升子序列(高频)

    首先我们分析题目,要找的是最长上升子序列(Longest Increasing Subsequence,LIS)。因为题目中没有要求连续,所以 LIS可能是连续...

    程序员小浩
  • 漫画:BAT必考题目 (如何压缩状态完成不同路径题目)

    不同路径:一个机器人位于一个 m x n 网格的左上角,起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,在下...

    程序员小浩
  • 《剑指offer》第25天:最简单的动态规划

    这种思想的本质是:一个规模比较大的问题(可以用两三个参数表示的问题),可以通过若干规模较小的问题的结果来得到的(通常会寻求到一些特殊的计算逻辑,如求最值等),如...

    程序员小浩
  • 打卡群刷题总结0805——不同的二叉搜索树

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • Leetcode 72 Edit Distance DP好题

    Given two words word1 and word2, find the minimum number of steps required to c...

    triplebee
  • LeetCode 44. 通配符匹配(DP)

    给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。

    Michael阿明
  • 【leetcode刷题】T164-完全平方数

    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

    木又AI帮
  • 【leetcode刷题】T157-不同路径 II

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    木又AI帮
  • 画解算法:70. 爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    灵魂画师牧码
  • 打卡群刷题总结0923——完全平方数

    链接:https://leetcode-cn.com/problems/perfect-squares

    木又AI帮

扫码关注云+社区

领取腾讯云代金券