python如何求数组连续最大和的示例代码
题目描述：
一个有n个元素的数组，这n个元素既可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组的最大值。例如，对于数组[1，-2，4，8，-4，7，-1，-5]而言，其最大和的子数组为[4,8,-4,7]，最大值为15。
方法：
- 蛮力法
- 重复利用已经计算的子数组和
- 动态规划
- 优化的动态规划
1.蛮力法
找出所有的子数组，然后求出子数组的和，在所有子数组的和中取最大值。
代码实现：
#!/usr/bin/envpython3
#-*-coding:utf-8-*-
#@Time:2020/1/2921:59
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
defmaxSubArrSum(arr):
ifarr==Noneorlen(arr)<=0:
print('参数不合理！')
return
thisSum=0
maxSum=0
i=0
whileimaxSum:
maxSum=thisSum
j+=1
i+=1
returnmaxSum
if__name__=='__main__':
arr=[1,-2,4,8,-4,7,-1,-5]
print('1maxsubarraysum:',maxSubArrSum(arr))
结果：
算法性能分析：
这种方法的时间复杂度为O(n3)；
2.重复利用已经计算的子数组和
由于sum[i，j]=sum[i，j-1]+arr[j]，在计算sum[i，j]的时候可以使用前面已计算出的sum[i，j-1]而不需要重新计算，采用这种方法可以省去计算sum[i，j-1]的时间，从而提高效率。
代码实现：
#!/usr/bin/envpython3
#-*-coding:utf-8-*-
#@Time:2020/1/3010:53
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
defmaxSubArrSum(arr):
ifarr==Noneorlen(arr)<=0:
print('参数不合理！')
return
maxSum=-2**31
i=0
whileimaxSum:#每加一次就判断一次
maxSum=sums
j+=1
i+=1
returnmaxSum
if__name__=='__main__':
arr=[1,-2,4,8,-4,7,-1,-5]
print('2maxsubarraysum:',maxSubArrSum(arr))
结果：
算法性能分析：
使用了双重循环，时间复杂度为O(n2)；
3.动态规划
首先可以根据数组最后一个元素arr[n-1]与最大子数组的关系分为以下三种情况讨论：
(包含或不包含，包含的话肯定以最后一个元素结尾；不包含的话，或者最后一个元素单独构成最大子数组，或者转换为求arr[1…n-2]的最大子数组)
(1)最大子数组包含arr[n-1]，即最大子数组以arr[n-1]结尾；
(2)arr[n-1]单独构成最大子数组；
(3)最大子数组不包含arr[n-1]，那么求arr[1…n-1]的最大子数组可以转换为求arr[1…n-2]的最大子数组。
所以有：
代码实现：
#!/usr/bin/envpython3
#-*-coding:utf-8-*-
#@Time:2020/1/3011:19
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
defmaxSubArrSum(arr):
ifarr==Noneorlen(arr)<=0:
print('参数不合理！')
return
n=len(arr)
End=[None]*n#End[i]表示包含arr[i]的最大子数组和
All=[None]*n#All[i]表示最大子数组和
End[n-1]=arr[n-1]
All[n-1]=arr[n-1]
End[0]=All[0]=arr[0]
i=1
whilei
结果：
算法性能分析：
时间复杂度为O(n)；
由于额外申请了两个数组，所以空间复杂度为O(n)；
4.优化的动态规划
方法3中每次其实只用到了End[i-1]与All[i-1]，而不是整个数组中的值，所以可以定义两个变量来保存End[i-1]与All[i-1]的值，并且可以反复利用。
代码实现：
#!/usr/bin/envpython3
#-*-coding:utf-8-*-
#@Time:2020/1/3011:55
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
defmaxSubArrSum(arr):
ifarr==Noneorlen(arr)<=0:
print('参数不合理！')
return
nAll=arr[0]#最大子数组和
nEnd=arr[0]#包含最后一个元素的最大子数组和
i=1
whilei
结果：
算法性能分析：
时间复杂度为O(n)；
空间复杂度为O(1)；
引申：
在知道了子数组的最大值后，如何确定最大子数组的和？
思路：
代码实现：
#!/usr/bin/envpython3
#-*-coding:utf-8-*-
#@Time:2020/1/3012:01
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
classTest:
def__init__(self):
self.begin=0#记录最大子数组起始位置
self.end=0#记录最大子数组结束位置
defmaxSubArrSum(self,arr):
n=len(arr)
maxSum=-2**31#子数组最大值
nSum=0#包含子数组最后一位的最大值
nStart=0
i=0
whileimaxSum:
maxSum=nSum
self.begin=nStart
self.end=i
i+=1
returnmaxSum
defgetBegin(self):
returnself.begin
defgetEnd(self):
returnself.end
if__name__=='__main__':
arr=[1,-2,4,8,-4,7,-1,-5]
t=Test()
print('连续最大和为:',t.maxSubArrSum(arr))
print('beginat',t.getBegin())
print('endat',t.getEnd())
结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。