Python|动态规划之最大子序和

题目描述给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1]的和最大,为 6。解决方案对于此题,将采用动态规划进行分析:对数组的每一个下标所能得到的最大值进行记录;通过判断上一个下标的最大值是否大于0,大于0则用当前下标所对应的值加上上一个下标。反之,小于则不取上一个下标的最大值(因为若是上一个下标所对应的数组最大值小于0,那么当前下标的数组最大和就等于它本身)。动态递推公式:dp[i] = max(dp[i-1], 0)+nums[i]代码示例:class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0 for _ in range(len(nums))]dp[0], max_sums = nums[0], nums[0]for i in range(1, len(nums)):dp[i] = max(dp[i-1], 0)+nums[i]max_sums = max(max_sums, dp[i])return max_sums结语本题是一道简单的动态规划的题目,更多的是对动态规划的理解与记忆,希望对读者有所帮助。主  编   |   王楠岚责  编   |   WZY能力越强,责任越大。实事求是,严谨细致。——where2go 团队微信号:算法与编程之美

(0)

相关推荐

  • ​LeetCode刷题实战53:最大子序和

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • (1条消息) 动态规划就此一篇 全网最详细, 逐步理解, 万字总结

    文章目录 动态规划 - 超详细系列 首先,先大致列下这篇文章会讲到什么 1.相较于暴力解法,动态规划带给我们的是什么?为什么会有重叠子问题以及怎么去避免的? 2.用不同难度的动态规划问题举例说明, 最 ...

  • ​LeetCode刷题实战312:戳气球

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • Leetcode刷题 2021.01.24

    Leetcode674 最长连续递增序列 给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度. 连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于 ...

  • 动态规划答疑篇

    ----------- 这篇文章就给你讲明白两个问题: 1.到底什么才叫「最优子结构」,和动态规划什么关系. 2.为什么动态规划遍历 dp 数组的方式五花八门,有的正着遍历,有的倒着遍历,有的斜着遍历 ...

  • 干货:图解算法——动态规划系列

    动态规划系列一:爬楼梯 1.1 概念讲解 讲解动态规划的资料很多,官方的定义是指把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解.概念中的各阶段之间的关系,其实指的就是状态转移方程. ...

  • 剑指offer

    03 数组中重复的数字 public int findRepeatNumber(int[] nums){ //排序后的数组,重复元素必然相邻 Arrays.sort(nums); //结果集 int ...

  • (1条消息) 动态规划入门看这篇就够了,万字长文!

    今天是小浩算法 "365刷题计划" 动态规划 - 整合篇.大家应该期待已久了吧!奥利给! 01 PART 动态规划是啥 我们把要解决的一个大问题转换成若干个规模较小的同类型问题,当 ...

  • 「C语言程序设计」C语言获取矩阵的最大值及其下标

    本实例要求使用二维数组将一个 3×4 的矩阵中所有元素的最大值及其下标获取,通过该程序,掌握二维数组的引用知识. 算法思想 针对本实例,有两个步骤需要编写程序完成: ✿ 第一个步骤是求矩阵元素的最大值 ...

  • ​LeetCode刷题实战410:分割数组的最大值

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 这个前端竟然用动态规划写瀑布流布局?给我打死他!

    前言 瀑布流布局是前端领域中一个很常见的需求,由于图片的高度是不一致的,所以在多列布局中默认布局下很难获得满意的排列. 我们的需求是,图片高度不规律的情况下,在两列布局中,让左右两侧的图片总高度尽可能 ...

  • ​LeetCode刷题实战152:乘积最大子数组

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...