您好,登录后才能下订单哦!
题目描述:
一个有 n 个元素的数组,这 n 个元素既可以是正数也可以是负数,数组中连续
的一个或多个元素可以组成一个连续的子数组,一个数组可能有多个这种连续的子数组,求子数组的最大值。例如,对于数组 [1,-2,4,8,-4,7,-1,-5] 而言,其最大和的子数组为 [4,8,-4,7],最大值为 15。
方法:
1.蛮力法
找出所有的子数组,然后求出子数组的和,在所有子数组的和中取最大值。
代码实现:
#!/usr/bin/env python3 # -*- coding: utf-8 -*- # @Time : 2020/1/29 21:59 # @Author : buu # @Software: PyCharm # @Blog :https://blog.csdn.net/weixin_44321080 def maxSubArrSum(arr): if arr == None or len(arr) <= 0: print('参数不合理!') return thisSum = 0 maxSum = 0 i = 0 while i < len(arr): j = i while j < len(arr):# j 控制连续子数组包含的元素个数 thisSum = 0 k = i # k 表示连续子数组开始的下标 while k < j: thisSum += arr[k] k += 1 if thisSum > maxSum: maxSum = thisSum j += 1 i += 1 return maxSum if __name__ == '__main__': arr = [1, -2, 4, 8, -4, 7, -1, -5] print('1 max sub array sum:', 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/env python3 # -*- coding: utf-8 -*- # @Time : 2020/1/30 10:53 # @Author : buu # @Software: PyCharm # @Blog :https://blog.csdn.net/weixin_44321080 def maxSubArrSum(arr): if arr == None or len(arr) <= 0: print('参数不合理!') return maxSum = -2 ** 31 i = 0 while i < len(arr): # i: 0~7 sums = 0 j = i while j < len(arr): # j: 0~7 sums += arr[j] # sums 重复利用 if sums > maxSum: # 每加一次就判断一次 maxSum = sums j += 1 i += 1 return maxSum if __name__ == '__main__': arr = [1, -2, 4, 8, -4, 7, -1, -5] print('2 max sub array sum:', 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/env python3 # -*- coding: utf-8 -*- # @Time : 2020/1/30 11:19 # @Author : buu # @Software: PyCharm # @Blog :https://blog.csdn.net/weixin_44321080 def maxSubArrSum(arr): if arr == None or len(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 while i < n: End[i] = max(End[i - 1] + arr[i], arr[i]) # i=1时若arr[0]<0,则从arr[1]重新开始 All[i] = max(End[i], All[i - 1]) i += 1 return All[n - 1] if __name__ == '__main__': arr = [1, -2, 4, 8, -4, 7, -1, -5] print('3 max sub array sum:', maxSubArrSum(arr))
结果:
算法性能分析:
时间复杂度为O(n);
由于额外申请了两个数组,所以空间复杂度为O(n);
4.优化的动态规划
方法3中每次其实只用到了 End[i-1] 与 All[i-1] ,而不是整个数组中的值,所以可以定义两个变量来保存 End[i-1] 与 All[i-1] 的值,并且可以反复利用。
代码实现:
#!/usr/bin/env python3 # -*- coding: utf-8 -*- # @Time : 2020/1/30 11:55 # @Author : buu # @Software: PyCharm # @Blog :https://blog.csdn.net/weixin_44321080 def maxSubArrSum(arr): if arr == None or len(arr) <= 0: print('参数不合理!') return nAll = arr[0] # 最大子数组和 nEnd = arr[0] # 包含最后一个元素的最大子数组和 i = 1 while i < len(arr): nEnd = max(nEnd + arr[i], arr[i]) nAll = max(nEnd, nAll) i += 1 return nAll if __name__ == '__main__': arr = [1, -2, 4, 8, -4, 7, -1, -5] print('4 max sub array sum:', maxSubArrSum(arr))
结果:
算法性能分析:
时间复杂度为O(n);
空间复杂度为O(1);
引申:
在知道了子数组的最大值后,如何确定最大子数组的和?
思路:
代码实现:
#!/usr/bin/env python3 # -*- coding: utf-8 -*- # @Time : 2020/1/30 12:01 # @Author : buu # @Software: PyCharm # @Blog :https://blog.csdn.net/weixin_44321080 class Test: def __init__(self): self.begin = 0 # 记录最大子数组起始位置 self.end = 0 # 记录最大子数组结束位置 def maxSubArrSum(self, arr): n = len(arr) maxSum = -2 ** 31 # 子数组最大值 nSum = 0 # 包含子数组最后一位的最大值 nStart = 0 i = 0 while i < n: if nSum < 0: nSum = arr[i] nStart = i else: nSum += arr[i] if nSum > maxSum: maxSum = nSum self.begin = nStart self.end = i i += 1 return maxSum def getBegin(self): return self.begin def getEnd(self): return self.end if __name__ == '__main__': arr = [1, -2, 4, 8, -4, 7, -1, -5] t = Test() print('连续最大和为:', t.maxSubArrSum(arr)) print('begin at ', t.getBegin()) print('end at ', t.getEnd())
结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持亿速云。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。