首页 > 代码库 > 求数组的子数组之和的最大值
求数组的子数组之和的最大值
《编程之美》的2.14中抛出了这么一道题。我的解法如下：
#!/usr/bin/env pythondef getMaxSubset(data): if len(data)==0: return curSum = maxSum = data[0] i = 1 while i < len(data): if curSum<=0: curSum = data[i] else: curSum+=data[i] if curSum>=maxSum: maxSum = curSum i+=1 return maxSuma1 = [-2, 5, 3, -6, 4, -8, 6]a2 = [-2, 3, -4]a3 = [1, -2, 3, 5, -3, 2]a4 = [0, -2, 3, 5, -1, 2]a5 = [-9, -8, -6, -5, -2]a6 = [0, 0, 0, 0]a7 = [-2,-3, 4,5,-2,6]print getMaxSubset(a1)print getMaxSubset(a2)print getMaxSubset(a3)print getMaxSubset(a4)print getMaxSubset(a5)print getMaxSubset(a6)print getMaxSubset(a7)
输出为：
8389-2013这样只需要扫描一遍数组，时间复杂度为O(N).
求数组的子数组之和的最大值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。