Python实现最大子序和的方法示例
作者:神不烦 时间:2023-04-08 03:30:38
描述
给定一个序列(至少含有 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
标签:Python,最大子序和
0
投稿
猜你喜欢
ASP存储过程开发应用详解第1/2页
2011-04-07 11:16:00
可以随便改别人的网页的代码
2008-03-25 12:54:00
python网页请求urllib2模块简单封装代码
2021-07-31 02:03:55
将Python的Django框架与认证系统整合的方法
2022-05-09 20:33:15
Oracle 游标使用总结
2024-01-24 01:26:52
golang copy函数使用的坑
2023-07-09 19:53:44
Python实现两款计算器功能示例
2023-01-18 06:18:39
Java常用正则表达式验证类完整实例【邮箱、URL、IP、电话、身份证等】
2022-09-14 05:59:39
让所有IE支持HTML5的解决方案
2009-10-31 18:43:00
django实现将修改好的新模型写入数据库
2024-01-28 19:50:13
Python 实现选择排序的算法步骤
2023-04-01 18:28:53
python图片水印加密的几种处理小结
2023-12-26 16:23:37
Python 概率生成问题案例详解
2023-11-26 19:04:58
Go语言单元测试模拟服务请求和接口返回
2024-04-23 09:41:13
Python 错误和异常小结
2021-08-19 12:17:58
我的ImageMagick使用心得
2008-10-21 11:05:00
详解MySQL数据库千万级数据查询和存储
2024-01-16 18:53:20
MySQL中datetime时间字段的四舍五入操作
2024-01-28 08:00:40
Golang调用FFmpeg转换视频流的实现
2024-04-30 10:01:43
vue阻止页面回退的实现方法(浏览器适用)
2024-06-07 15:24:10