Leetcode 053 最大子序和 python 分治+动态规划

2023-12-25 06:58

本文主要是介绍Leetcode 053 最大子序和 python 分治+动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

 

思路:

首先我们分析题目,我们思考,为什么最大和的连续子数组不包含其他的元素而是这几个呢?因为如果我们想在现有的基础上去扩展当前连续子数组,相邻的元素是一定要被加入的,而相邻元素中可能会减损当前的和。

思路一:

遍历法,On:

算法过程:遍历数组,用onesum去维护当前元素加起来的和。当onesum出现小于0的情况时,我们把它设为0。然后每次都更新全局最大值。

class Solution:def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""#onesum维护当前的和onesum = 0maxsum = nums[0]for i in range(len(nums)):onesum += nums[i]maxsum = max(maxsum, onesum)#出现onesum<0的情况,就设为0,重新累积和if onesum < 0:onesum = 0return maxsum

算法证明:一开始思考数组是个空的,把我们每次选一个nums[i]加入onesum看成当前数组新增了一个元素,也就是用动态的眼光去思考。过程很简单,代码很短,但为什么这样就能达到效果呢?我们进行的加和是按顺序来的,从数组第一个开始加。

当我们的i选出来后,加入onesum。这时有2种情况

1)假设我们这个onesum一直大于0,从未被<0过。那也就是说我们计算的每一次的onesum都大于0,而每一次计算的onesum都是包括开头元素的一段子序列(尾部一直随i变化)。看似我们没有考虑所有可能序列,但实际上所有可能的序列都已经被考虑过了。这里简单讲一下,待会po原文。

   a)以当前子序列开头为开头,中间任一处结尾的序列。这种情况是一直在扫描的,也有一直保存更新,所以不用怕丢失信息。

   b)以当前子序列结尾为结尾,中间任一处开头的序列。这种情况一定的和小于以当前子序列开头为开头,结尾为结尾的序列。因为前面缺失的那一段经过我们的前提,它也是加和大于0的。

   c)以中间元素为开头和结尾的序列。和小于以当前子序列开头为开头,此分序列结尾为结尾的序列。因为前面缺失的那一段经过我们的前提,它也是加和大于0的。

 

2)出现小于0的情况,就说明我们当前形成的这个子序是第一次出现小于0的情况。现在至少我们要新形成的连续数组不能在整个的包括之前的连续子序了,因为我们在之前的那个连续子序里加出了<0的情况。但问题是我们需不需要保留一些呢?是不是所有以当前子序结尾为结尾的任意开头的子序都要被舍弃呢?答案是是的,因为那一段也一定小于0,因为那一段的加和会小于以当前子序开头为开头,当前子序结尾为结尾的序列(见前面证明)。于是抛弃掉它们,重新开始新的子序。

 

思路二:

动态规划 On

算法过程:

设sum[i]为以第i个元素结尾的最大的连续子数组的和。假设对于元素i,所有以它前面的元素结尾的子数组的长度都已经求得,那么以第i个元素结尾且和最大的连续子数组实际上,要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素,要么是只包含第i个元素,即sum[i]
= max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择,而这实际上等价于判断sum[i-1]是否大于0。由于每次运算只需要前一次的结果,因此并不需要像普通的动态规划那样保留之前所有的计算结果,只需要保留上一次的即可,因此算法的时间和空间复杂度都很小

 


class Solution:def maxSubArray(self, nums):  """ :type nums: List[int] :rtype: int """  length=len(nums)  for i in range(1,length):  #当前值的大小与前面的值之和比较,若当前值更大,则取当前值,舍弃前面的值之和  subMaxSum=max(nums[i]+nums[i-1],nums[i])  nums[i]=subMaxSum#将当前和最大的赋给nums[i],新的nums存储的为和值  return max(nums)

算法证明:这道题的代码我直接使用了题目数据中的nums数组,因为只要遍历一遍。nums[i]表示的是以当前这第i号元素结尾(看清了一定要包含当前的这个i)的话,最大的值无非就是看以i-1结尾的最大和的子序能不能加上我这个nums[i],如果nums[i]>0的话,则加上。注意我代码中没有显式地去这样判断,不过我的Max表达的就是这个意思,然后我们把nums[i]确定下来。

 

思路三:

分治递归

算法过程:

分治法,最大子序和要么在左半部分,要么在右半部分,要么就横跨两部分(即包括左半部分的最后一个元素,和右半部分的第一个元素)。返回这三种情况的最大值即可。第三种情况,其中包括左半部分最后一个元素的情形,需要挨个往前遍历,更新最大值。包含右半部分的第一个元素的情况类似。总的时间复杂度O(nlogn)

 

class Solution(object):def maxSubArray(self, nums):#主函数left = 0#左右边界right = len(nums)-1#求最大和maxSum = self.divide(nums,left,right)return maxSumdef divide(self,nums,left,right):#如果只有一个元素就返回if left==right:return nums[left]#确立中心点center = (left+right)//2#求子序在中心点左边的和leftMaxSum = self.divide(nums,left,center)#求子序在中心点右边的和rightMaxSum = self.divide(nums,center+1,right)#求子序横跨2边的和,分成左边界和和右边界和leftBorderSum = nums[center]leftSum = nums[center]for i in range(center-1,left-1,-1):leftSum += nums[i]if leftSum>leftBorderSum:#不断更新左区块的最大值leftBorderSum = leftSumrightBorderSum = nums[center+1]rightSum = nums[center+1]for i in range(center+2,right+1):rightSum += nums[i]if rightSum>rightBorderSum:#不断更新右区块的最大值rightBorderSum = rightSum#左边界的和 + 右边那块的和BorderSum = leftBorderSum + rightBorderSumreturn max(leftMaxSum,rightMaxSum,BorderSum)

算法证明:

总的来说还是超级巧妙的。不断的切不断的切数组,把一块数组看成左中右三个部分。实际上这有点像枚举,但我们在枚举时利用了二分的思路,优化了很多。所以枚举当然可以达到我们的目标了,因为我们不断在计算以一定包括中间节点的子序的最大和。

 

总结:

今天写了很多很多,都没时间复习了。。。但是收获还是很大的。比如动态规划,不一定一定要建立数组然后返回数组的最后一项,动态规划其实是很灵活的。但是动态规划的每一项代表的意义要想好。

分治递归,实际在帮我们算所有数组只不过用了二分的思路优化。

 


作者:我喝酸奶不舔盖
来源:CSDN
原文:https://blog.csdn.net/weixin_41958153/article/details/81131379

这篇关于Leetcode 053 最大子序和 python 分治+动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/534605

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl