最大总和子列表？

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