最大总和子列表？

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

实际上,使用动态编程实现了非常优雅,非常有效的解决方案.它需要O(1)空间和O(n)时间 - 这不能被击败!

定义A为输入数组(零索引),并且B[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

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

根据问题，如果列表中的所有元素均为负数，则应将最大总和返回为“零”

相反，如果您希望输出为子数组的最大值（负数），那么下面的代码将有所帮助：

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 4

它要求您选择列表中较小的子部分，以使较小子部分的总和最大。

如果列表都是正数，[1 2 3]那么当然，总和最大的子部分就是整个列表的总和[1 2 3]，即 6。

如果列表都是负数，[-1 -2 -3]那么总和最大的子部分就不是[]总和为 0 的子节。

然而，如果列表中有一些积极的内容，也有一些消极的内容，那么做出决定就更困难了

[1 2 3 -100 3 4 5]你应该看到[3 4 5]并返回 12

[1 2 3 -2 3 4 5]你应该使用全部并返回 16