我对它的问题感到困惑.
写入函数
mssl()(最小和子列表),将整数列表作为输入.然后,它计算并返回输入列表的最大总和子列表的总和.最大总和子列表是输入列表的子列表(切片),其条目总和最大.空子列表定义为总和0.例如,列表的最大总和子列表[4, -2, -8, 5, -2, 7, 7, 2, -6, 5]是[5, -2, 7, 7, 2]其条目的总和19.
如果我要使用这个函数,它应该返回类似的东西
>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
>>> mssl(l)
19
>>> mssl([3,4,5])
12
>>> mssl([-2,-3,-5])
0
我该怎么做？
这是我目前的尝试,但它不会产生预期的结果:
def mssl(x):
' list ==> int '
res = 0
for a in x:
if a >= 0:
res = sum(x)
return res
else:
return 0
下面的代码实现了O(n ^ 2)的时间复杂度.我希望能够在O(n)中完成.
例如,给定数组[-2,1,-3,4,-1,2,1,-5,4],连续子阵列[4,-1,2,1]具有最大的和= 6.
def maximum_sub_array(arr, n):
ans = - sys.maxint - 1
for start_index in range(0, n):
_sum = 0
for sub_array_size in range(1,n+1):
if (start_index + sub_array_size > n): # Subarray exceeds array bounds
break
_sum += arr[start_index + sub_array_size -1] # Last element of the new Subarray
ans = max(ans, _sum)
return ans