最大和子列表？
我被这个问题搞糊涂了，因为它想问什么。
编写函数
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回答 13
Stack Overflow用户
发布于 2013-02-25 09:06:07
实际上，使用动态规划有一个非常优雅、非常有效的解决方案。它需要O(1)空间和O(n) time --这是不可战胜的！
将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])
19Stack Overflow用户
发布于 2013-02-26 07:30:07
我是最大子数组问题。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_farStack Overflow用户
发布于 2017-09-08 09:46:41
根据这个问题，如果列表中的所有元素都为负数，则应将最大和返回为“零”。
相反，如果要将输出作为子数组的最大值(以负数表示)，则下面的代码将有所帮助：
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]: 19https://stackoverflow.com/questions/15062844
复制相似问题
腾讯云开发者
