好资源导航 » 文章资讯 » python求最大连续子数组的和

python求最大连续子数组的和

2023-09-10 14:48:05 57

抛出问题：

求一数组如l=[0,1,2,3,-4,5,-6]，求该数组的最大连续子数组的和如结果为[0,1,2,3,-4,5]的和为7

问题分析：

这个问题很简单，直接暴力法，上代码。

#-*-coding:utf-8-*-
#日期：2018/6/97:46
#Author:小鼠标

#最大连续子数组的和
l=[0,1,2,3,-4,5,-6]
#暴力求解
defviolence(l=[]):
maxVal=0
x,y=0,0
foriinrange(0,len(l)+1):
forjinrange(0,len(l)+1):
res=sum(l[i:j])
ifres>maxVal:
maxVal=res
x=i
y=j
returnmaxVal,x,y
maxVal,x,y=violence(l)
print(maxVal,(x,y))

分治法：

关键是暴力法的时间复杂度太高，所以就在原有的基础上做了进一步的提升--分治法。

所谓分治法就是将原有的列表一分为二，那么最大的子列表只有三种情况：

1、最大子列表完全在左边

2、最大子列表完全在右边

3、最大子列表跨立在中间

所以我们分情况讨论，求出答案。这种方法一定程度的降低了时间复杂度，从之前的n^2降到了(n/2)^2+2n

#-*-coding:utf-8-*-
#日期：2018/6/97:46
#Author:小鼠标

#最大连续子数组的和
l=[0,1,2,3,-4,5,-6]
#暴力求解
defviolence(l=[]):
maxVal=0
x,y=0,0
foriinrange(0,len(l)+1):
forjinrange(0,len(l)+1):
res=sum(l[i:j])
ifres>maxVal:
maxVal=res
x=i
y=j
returnmaxVal,x,y
#分治法想左扫向右扫,求出两边的最大值
defleft_or_right(l):
maxVal=0
term=0
foriinl:
term+=i
ifmaxVal
动态规划：


即便是分治法，时间复杂度还是太高，不满足生产的需求，所以如果说只求最大子序列的和的值而不去追求最大子序列本身，我们又引出一个方法--动态规划


这种方法的时间复杂是是线性的，极大的降低了。


#-*-coding:utf-8-*-
#日期：2018/6/98:38
#Author:小鼠标

deffunction(lists):
max_sum=lists[0]
pre_sum=0
foriinlists:
#因为最大子列表一定是从一个非0的数开始的（假定列表中有正数有负数）
#所以就可以暂时筛选调小于0的数，即便列表全是负数，那么最大的子列表肯定是负数最大的一个
ifpre_sum<0:
pre_sum=i
else:
pre_sum+=i
ifpre_sum>max_sum:
max_sum=pre_sum
returnmax_sum
lists=[0,1,2,3,-4,5,-6]
print(function(lists))


以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

返回顶部
514930285
czq8825@qq.com

python求最大连续子数组的和

热门推荐

随机推荐