最大子数组和
2021-06-22 23:05
标签：循环 else 定义 长度 子序列 连续子序列 计算机 class 时间复杂度 题目描述 首先看到这题脑袋里还是想的是枚举所有连续组合求和的方式，假如有n个数，连续一个数字以上可以组合，那一共就有8+7+6+5+4+3+2+1=36种方式，即n*(n+1)/2,故时间复杂度还是为O(n2)。o(╯□╰)o 换一种方式，依次从前往后扫描，定义两个变量，一个记录之前连续子数组的和 continueSum，另一个记录之前子数组的最大和 maxSubSum，如果当 array[i]+continueSum 如果之前连续子数组和与当前位置的和还小于当前值，则意味着之前子数组和为负，连续子数组的和就为当前的值，同时，每次进入循环时判断continueSum+array[i] >maxSubSum是否成立，成立则更新maxSubSum。 完整python代码如下: 最大子数组和 标签：循环 else 定义 长度 子序列 连续子序列 计算机 class 时间复杂度 原文地址：https://www.cnblogs.com/tangsmarth/p/9675958.html
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,
常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,
并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)class Solution:
continueSum = 0
maxSubSum = 0
def FindGreatestSumOfSubArray(self, array):
if max(array)0:
return max(array)
for i in range(len(array)):
if self.continueSum+array[i]>self.maxSubSum:
self.maxSubSum = self.continueSum + array[i]
if self.continueSum+array[i]array[i]:
self.continueSum = array[i]
else:
self.continueSum += array[i]
return self.maxSubSum
# array = [6,-3,-2,7,-15,1,2,2]
array = [1,-2,3,10,-4,7,2,-5]
s = Solution()
print(s.FindGreatestSumOfSubArray(array))