Python实现最大子序和的方法示例
作者:神不烦 发布时间:2023-04-08 03:30:38
标签:Python,最大子序和
描述
给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。
例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4],
连续子序列 [4,-1,2,1] 的和最大,为 6。
我 v1.0
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
i = 0
result = nums[0]
while i < l:
sums = []
temp = 0
for j in range(i, l):
temp+=nums[j]
sums.append(temp)
if result < max(sums):
result = max(sums)
i+=1
return result
测试结果如下:
本地运行时间为14.7s,说明我的方法太粗暴了。应该寻找更好的算法。
我 优化后v1.1。优化方案,去掉sums数组,节省空间。但时间复杂度仍然不变。
l = len(nums)
i = 0
result = nums[0]
while i < l:
temp = 0
for j in range(i, l):
temp+=nums[j]
if result < temp:
result = temp
i+=1
return result
仍然只通过200/202测试用例,仍然超出时间限制。但本地运行时间为8.3s。有进步。
别人,分治法。时间复杂度O(NlogN)
将输入的序列分成两部分,这个时候有三种情况。
1)最大子序列在左半部分
2)最大子序列在右半部分
3)最大子序列跨越左右部分。
前两种情况通过递归求解,第三种情况可以通过。
分治法代码大概如下,emmm。。。目前还没有完全理解。
def maxC2(ls,low,upp):
#"divide and conquer"
if ls is None: return 0
elif low==upp: return ls[low]
mid=(low+upp)/2 #notice: in the higher version python, “/” would get the real value
lmax,rmax,tmp,i=0,0,0,mid
while i>=low:
tmp+=ls[i]
if tmp>lmax:
lmax=tmp
i-=1
tmp=0
for k in range(mid+1,upp):
tmp+=ls[k]
if tmp>rmax:
rmax=tmp
return max3(rmax+lmax,maxC2(ls,low,mid),maxC2(ls,mid+1,upp))
def max3(x,y,z):
if x>=y and x>=z:
return x
return max3(y,z,x)
动态规划算法,时间复杂度为O(n)。
分析:寻找最优子结构。
l = len(nums)
i = 0
sum = 0
MaxSum = nums[0]
while i < l:
sum+=nums[i]
if sum > MaxSum:
MaxSum = sum
if sum < 0:
sum = 0
i+=1
return MaxSum
Oh!My god!!! !!!!!!!!运行只花了0.2s!!!!!!!!!!!!!!!这也太强了吧!!
优化后,运行时间0.1s.
sum = 0
MaxSum = nums[0]
for i in range(len(nums)):
sum += nums[i]
if sum > MaxSum:
MaxSum = sum
if sum < 0:
sum = 0
return MaxSum
其中
sum += nums[i]
必须紧挨。
MaxSum = sum
来源:https://blog.csdn.net/qq_34364995/article/details/80284270
0
投稿
猜你喜欢
- XML的嵌套处理 一般情况下,我们从数据库中查询得到的结果集可能很大,所以从服务器返回到客户端时,数据会被分成若干个页面分别进行传递。此时,
- 常用当前循环.作用default数据为空时设置默认值length取变量长度filesizeformat文件大小转成可读slice从指定位置到
- Python画图(线条颜色、大小、线形)先放基础代码,下面讲述效果:import matplotlib.pyplot as pltimpor
- 本文实例为大家分享了python绘制分组对比柱状图的具体代码,供大家参考,具体内容如下首先放效果图: # -*- co
- 现在用python画图已经难不倒一直跟小编学习的小伙伴们了,甚至有的小伙伴画图比小编还要厉害。为此小编还偷偷下了一番功夫,画图这种事情,细节
- 引言在前面的文章当中我们讨论的是 python3 当中早期的内嵌数据结构字典的实现,在本篇文章当中主要介绍在后续对于字典的内存优化。字典优化
- 在document.form1.submit();后加document.body.innerHtml = "W
- 1,查看py文件内的所有成员及快速定位到代码块如果你的py文件代码超过200行,一定要采用这个方法,能大大提高你的代码查找效率。方法1:(1
- 看lifesinger的《由Kimi找茬想到的》,我想到的:1、 我不同意将“合并付款”定调在“很多卖家都需要”。这个“很多”在卖家里面大概
- 本文也是开发项目中的一个小经验Tip,虽然很简单,但对很多朋友也有小帮助。我们实际工程中,可能遇到开发环境、预上线环境、线上环境等环境场景,
- 这篇文章主要介绍了基于python实现文件加密功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可
- 本文实例讲述了Python遍历指定文件及文件夹的方法。分享给大家供大家参考。具体如下:初次编写:import osdef searchdir
- 如下所示:将i前面加str(i)就可以了补充拓展:python 连接字符串和数字 python 连接字符串和数字的问题:首先要说的
- 介绍当在图像上训练深度神经网络模型时,通过对由数据增强生成的更多图像进行训练,可以使模型更好地泛化。常用的增强包括水平和垂直翻转/移位、以一
- 这是一个网页设计中经常会用到的图片特效,实现多个图片之间的轮换,并分别带有连接。以前的代码只能适用于IE,在FF下始终没有得到很好的解决今天
- 如何在SQL中启用全文检索功能?本文将通过实例向你剖折这个问题。这是一个全文索引的一个例子,首先在查询分析器中使用:use pubsgo--
- 看到代码里面有这个1 class ResNeXt101(nn.Module): 2 def __init__(se
- 本文实例讲述了Python正则简单用法。分享给大家供大家参考,具体如下:悄悄打入公司内部UED的一个Python爱好者小众群,前两天一位牛人
- 一维插值插值不同于拟合。插值函数经过样本点,拟合函数一般基于最小二乘法尽量靠近所有样本点穿过。常见插值方法有拉格朗日插值法、分段插值法、样条
- 利用XMLHTTP无刷新自动实时更新数据,2秒自动刷新一次,2秒取得一次数据.demo.htm 前台显示<script la