专栏首页小浩算法漫画:动态规划系列 第二讲

漫画:动态规划系列 第二讲

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

01

第53题:最大子序和

第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[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语言示例

根据分析,得到代码:

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
}

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

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)。

注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过go。算法思想最重要,使用go纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!

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

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

原始发表时间:2020-01-27

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    程序员小浩
  • 动态规划入门看这篇就够了,万字长文!

    今天是小浩算法 “365刷题计划” 动态规划 - 整合篇。大家应该期待已久了吧!奥利给!

    程序员小浩
  • 漫画:动态规划系列 第三讲

    在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 "最大子序和",学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过...

    程序员小浩
  • 程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

    Michael阿明
  • Golang Leetcode 334. Increasing Triplet Subsequence.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89068924

    anakinsun
  • 详解三道一维的动态规划算法题

    在一条直线上,有n个房屋,每个房屋中有数量不等的财宝,有一个盗 贼希望从房屋中盗取财宝,由于房屋中有报警器,如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...

    帅地
  • 初级算法-动态规划

    动态规划主要是解一些递归问题,也就是将递归写成非递归方式,因为编辑器无法正确对待递归,递归方法会导致很多计算结果被重复计算,比如菲波那切数列。

    方丈的寺院
  • 算法细节系列(21):贪心有理?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

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

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

    程序员小浩
  • 力扣416——分割等和子集

    这道题主要涉及的是动态规划,类似背包问题,主要还是需要找出状态转移方程,优化时可以考虑采用深度优先搜索。

    健程之道

扫码关注云+社区

领取腾讯云代金券