最大总和子列表？
我对这个问题想要问什么感到困惑。
编写函数
mssl()（最小总和子列表）作为input的整数列表。 然后计算并返回input列表的最大总和子列表的总和。 最大总和子清单是input清单总和最大的子清单（分片）。 例如，列表[4, -2, -8, 5, -2, 7, 7, 2, -6, 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
实际上有一个非常优雅，非常有效的解决scheme，使用dynamic编程 。 它需要O（1）空间和O（n）时间 – 这是不能被打败的！
将A定义为input数组（zero-indexed）， 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)等等。 那么，显然，解决scheme是由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
这是最大的子arrays问题 。 Kadanealgorithm可以在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
所以如果你理解一个子列表是什么（或者一个切片，它可以被认为是同一件事情），切片是由开始索引和结束索引定义的。
所以，也许你可以尝试遍历所有可能的开始和结束索引，并计算相应的总和，然后返回最大值。
提示：开始索引可以从0到len(given_list)-1 。 结束索引可以从start_index到len(given_list)-1 。 你可以使用嵌套for循环来检查所有可能的组合。
下面是Java中的一个实现，使用Kadanealgorithm，它打印最大和的索引。 执行需要O（n）个时间和O（1）空间。
public static void maxSumIndexes(int[] a) { int size = a.length; if(size == 0) return; int maxAtIndex = a[0], max = a[0]; int bAtIndex = 0; int b = 0, e = 0; for(int i = 1; i < size; i++) { maxAtIndex = Math.max(a[i], a[i] + maxAtIndex); if(maxAtIndex == a[i]) bAtIndex = i; max = Math.max(max, maxAtIndex); if(max == maxAtIndex) { e = i; b = (b != bAtIndex)? bAtIndex : b; } } System.out.println(b); System.out.println(e); }
简单的解决scheme遍历列表，只是尝试添加切片，直到find最好的切片。 这里我还包括了返回实际子列表的选项，默认情况下这是False。 为了这个目的，我使用了defaultdict，因为它比查找更简单。
from collections import defaultdict def mssl(lst, return_sublist=False): d = defaultdict(list) for i in range(len(lst)+1): for j in range(len(lst)+1): d[sum(lst[i:j])].append(lst[i:j]) key = max(d.keys()) if return_sublist: return (key, d[key]) return key print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5]) 19 print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5], True) (19, [[5, -2, 7, 7, 2]])
奖励：列表理解方法：
def _mssl(lst): return max( sum( lst[i:j] ) for i in xrange(len(lst)+1) for j in xrange(i, len(lst)+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
这是要求你select一个较小的小部分，使小部分的总和是最大的。
如果列表全部是肯定的[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
我假设这是在数组中产生最大和的子序列的问题。 我在search最大总和SUBSET问题时遇到此问题。
这个问题的Java实现：
public static int maximumSumSubSequence(int[] array) { if (null == array) { return -1; } int maxSum = Integer.MIN_VALUE; int startIndexFinal = 0; int endIndexFinal = 0; int currentSum = 0; int startIndexCurrent = 0; for (int i = 0; i < array.length; i++) { currentSum += array[i]; if (currentSum > maxSum) { maxSum = currentSum; endIndexFinal = i; startIndexFinal = startIndexCurrent; } if (currentSum <= 0) { currentSum = 0; startIndexCurrent = i + 1; } } System.out.println("startIndex: " + startIndexFinal + " endIndex: " + endIndexFinal); return maxSum; }
这个区别可能对OP来说并不重要，OP似乎只是在试图理解如何解决这个问题，但我认为值得一提的是：
这里的其他解决scheme包括反复总结列表的所有子部分。 我们可以通过使用dynamic编程来避免这些重复的总和，因为当然，如果我们已经知道从i到j的总和，我们不需要再次叠加它们来获得从i到j+1的总和！
也就是说，做出部分和的二维数组，以使partsum[i, j] == sum(lst[i:j]) 。 像（使用字典，因为它更容易索引;一个numpy数组将会同样简单，更有效）：
import operator def mssl(lst, return_sublist=False): partsum = { (0, 0): 0 } # to correctly get empty list if all are negative for i in xrange(len(lst) - 1): # or range() in python 3 last = partsum[i, i+1] = lst[i] for j in xrange(i+1, len(lst)): last = partsum[i, j+1] = last + lst[j] if return_sublist: (i, j), sum = max(partsum.iteritems(), key=operator.itemgetter(1)) return sum, lst[i:j] return max(partsum.itervalues()) # or viewvalues() in 2.7 / values() in 3.x
这需要O（n ^ 2）时间和内存，而不是O（n ^ 3）时间和O（1）内存的Lev / Inbar的方法（如果没有像Inbar的第一个代码示例一样简单地实现）。
这篇文章介绍了三种方法来find一个数组的最大子arrays。
- 蛮力（O（n * n））
- 分而治之（O（nlgn））
- Kadanealgorithm（O（n））
其中，最快的是具有O（n）时间复杂度的Kadanealgorithm。
如果有人正在寻找一个更长的代码版本，这里是：
def mesl(lst): sub_sum = list() row_sum = list() for i in range(len(lst)): sub_sum = list() sub_sum.append(lst[i]) k = 1 for j in range(i+1,len(lst)): sub_sum.append(sub_sum[k-1] + lst[j]) k+=1 row_sum.append(max(sub_sum)) sum = max(row_sum) if sum < 0: sum = 0 return sum
