最大总和子列表？

Question

对于这个问题，我感到困惑。写函数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

Answer 1

这是最大的子阵列问题。Kadane的算法可以在O(n)时间和O(1)空间上求解它，其过程如下：

def mssl(x):

    max_ending_here = max_so_far = 0

    for a in x:

        max_ending_here = max(0, max_ending_here + a)

        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far