{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?(子向量的长度至少是1)
最优方法,时间复杂度O(n),和最大的子序列的第一个元素肯定是正数 ,因为元素有正有负,因此子序列的最大和一定大于0
def FindGreatestSumOfSubArray(self, array):
maxVal=array[0]
sumVal=0
for val in array:
sumVal+=val
if sumVal>maxVal:
maxVal=sumVal
# 如果累加和出现小于0的情况,
# 则和最大的子序列肯定不可能包含前面的元素,
# 这时将累加和置0,从下个元素重新开始累加
if sumVal<0:
sumVal=0
return maxVal