最大子列表和?

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

根据问题的描述，如果列表中的所有元素都是负数，那么应该返回的最大和是“零”。

如果你想要的输出是负数中子数组的最大值，那么下面的代码可以帮到你：

In [21]: def mssl(l):
...:     best = cur = l[0]
...:     for i in range(len(l)):
...:         cur = max(cur + l[i], l[i])
...:         best = max(best, cur)
...:     return best

示例：

In [23]: mssl([-6, -44, -5, -4, -9, -11, -3, -99])
Out[23]: -3
In [24]: mssl([-51, -23, -8, -2, -6])
Out[24]: -2

适用于正数和负数的情况

In [30]: mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
Out[30]: 19

Answer 2

这是一个叫做最大子数组问题的内容。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

Answer 3

其实有一个非常优雅且高效的解决方案，使用的是动态规划。它只需要O(1)的空间和O(n)的时间——这个效率真是没得比！

我们把输入的数组叫做A（从0开始计数），而B[i]表示所有以位置i结尾但不包括i的子列表的最大和（也就是说，所有的子列表A[j:i]）。因此，B[0] = 0，B[1] = max(B[0]+A[0], 0)，B[2] = max(B[1]+A[1], 0)，B[3] = max(B[2]+A[2], 0)，以此类推。这样，我们可以很清楚地得到答案就是max(B[0], ..., B[n])。

因为每个B的值只依赖于前一个B，所以我们可以不需要存储整个B数组，这样就实现了O(1)的空间需求。

使用这种方法，mssl就简化成一个非常简单的循环：

def mssl(l):
    best = cur = 0
    for i in l:
        cur = max(cur + i, 0)
        best = max(best, cur)
    return best

演示：

>>> mssl([3,4,5])
12
>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
19
>>> mssl([-2,-3,-5])
0

---

如果你还想要开始和结束的切片索引，你需要记录更多的信息（注意，这仍然是O(1)的空间和O(n)的时间，只是稍微复杂一点）：

def mssl(l):
    best = cur = 0
    curi = starti = besti = 0
    for ind, i in enumerate(l):
        if cur+i > 0:
            cur += i
        else: # reset start position
            cur, curi = 0, ind+1

        if cur > best:
            starti, besti, best = curi, ind+1, cur
    return starti, besti, best

这个方法返回一个元组(a, b, c)，使得sum(l[a:b]) == c并且c是最大的：

>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
(3, 8, 19)
>>> sum([4, -2, -8, 5, -2, 7, 7, 2, -6, 5][3:8])
19