Python 最大总和子列表？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15062844/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Maximum sum sublist?
提问by Jeff Rageo
I'm getting confused with this question at what it's trying to ask.
我对这个问题试图提出的问题感到困惑。
Write function
mssl()(minimum sum sublist) that takes as input a list of integers. It then computes and returns the sum of the maximum sum sublist of the input list. The maximum sum sublist is a sublist (slice) of the input list whose sum of entries is largest. The empty sublist is defined to have sum 0. For example, the maximum sum sublist of the list[4, -2, -8, 5, -2, 7, 7, 2, -6, 5]is[5, -2, 7, 7, 2]and the sum of its entries is19.
编写函数
mssl()（最小和子列表），将整数列表作为输入。然后计算并返回输入列表的最大总和子列表的总和。最大总和子列表是输入列表的条目总和最大的子列表（切片）。空子列表定义为总和为 0。例如，列表的最大总和子列表[4, -2, -8, 5, -2, 7, 7, 2, -6, 5]为[5, -2, 7, 7, 2]，其条目的总和为19。
If I were to use this function it should return something similar to
如果我要使用这个函数，它应该返回类似于
>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5]
>>> mssl(l)
19
>>> mssl([3,4,5])
12
>>> mssl([-2,-3,-5])
0
How can I do it?
我该怎么做？
Here is my current try, but it doesn't produce the expected result:
这是我目前的尝试，但没有产生预期的结果：
def mssl(x):
' list ==> int '
res = 0
for a in x:
if a >= 0:
res = sum(x)
return res
else:
return 0
回答by Ric
It's asking you to choose a smaller subsection of a list such that the smaller subsection's sum is the largest.
它要求您选择列表中较小的子部分，以便较小子部分的总和最大。
If the list is all positive [1 2 3]then of course the subsection with the largest sum is just the sum of the entire list [1 2 3]which is 6.
如果列表都是正的，[1 2 3]那么当然总和最大的部分就是整个列表的总和[1 2 3]，即 6。
If the list is all negative [-1 -2 -3]then the subsection with the largest sum is nothing []which has sum 0.
如果列表都是负数，[-1 -2 -3]那么总和最大的部分就是[]总和为 0 的部分。
However if the list has some positive and some negative the decision is harder
然而，如果列表有一些正面和一些负面的决定更难
[1 2 3 -100 3 4 5]you should see [3 4 5]and return 12
[1 2 3 -100 3 4 5]你应该看到[3 4 5]并返回 12
[1 2 3 -2 3 4 5]you should use all of it and return 16
[1 2 3 -2 3 4 5]你应该使用所有它并返回 16
回答by Lev Levitsky
So if you understand what a sublist is (or a slice, which can be assumed to be the same thing), the slice is defined by the start index and the end index.
因此，如果您了解子列表是什么（或切片，可以假定为同一事物），则切片由开始索引和结束索引定义。
So maybe you could try and iterate over all possible start and end indexes and compute the corresponding sum, then return the maximum one.
所以也许你可以尝试迭代所有可能的开始和结束索引并计算相应的总和，然后返回最大值。
Hint: the start index can vary from 0 to len(given_list)-1. The end index can be from start_indexto len(given_list)-1. You could use a nested forloop to check all possible combinations.
提示：起始索引可以从 0 到len(given_list)-1. 结束索引可以是 fromstart_index到len(given_list)-1。您可以使用嵌套for循环来检查所有可能的组合。
回答by Inbar Rose
The simple solution is iterate over the list and just try adding up slices till you find the best one. Here I also included the option to return the actual sublist as well, by default this is False. I used defaultdict for this purpose because it is simpler than lookups.
简单的解决方案是遍历列表，然后尝试将切片相加，直到找到最好的切片。在这里，我还包括返回实际子列表的选项，默认情况下这是 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]])
Bonus: List comprehension method:
奖励：列表理解方法：
def _mssl(lst):
return max( sum( lst[i:j] ) for i in xrange(len(lst)+1) for j in xrange(i, len(lst)+1) )
回答by Dougal
This distinction probably isn't important to the OP, who seems to be just trying to understand how to solve the problem at all, but I thought it was worth mentioning:
这种区别对于 OP 来说可能并不重要，他似乎只是想了解如何解决问题，但我认为值得一提的是：
The other solutions here involve repeatedly summing up all the subparts of the list. We can avoid these repeated sums by using dynamic programming, since of course if we already know the sum from ito jwe don't need to do add them up again to get the sum from ito j+1!
这里的其他解决方案涉及重复总结列表的所有子部分。我们可以通过使用动态编程来避免这些重复的总和，因为当然如果我们已经知道 from ito的总和，j我们就不需要再次将它们相加以获得 from ito的总和j+1！
That is, make a 2d array of the partial sums, so that partsum[i, j] == sum(lst[i:j]). Something like (using a dictionary because it's easier to index with; a numpy array would be equally easy and more efficient):
也就是说，制作部分和的二维数组，使得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
This takes O(n^2) time and memory, as opposed to O(n^3) time and O(1) memory for Lev/Inbar's approach (if not implemented sillily like Inbar's first code example).
这需要 O(n^2) 时间和内存，而不是 Lev/Inbar 方法的 O(n^3) 时间和 O(1) 内存（如果没有像 Inbar 的第一个代码示例那样愚蠢地实现）。
回答by nneonneo
There's actually a very elegant, very efficient solution using dynamic programming. It takes O(1) space, and O(n) time-- this can't be beat!
实际上有一个使用动态编程的非常优雅、非常有效的解决方案。它需要O(1) 空间和O(n) 时间——这是无与伦比的！
Define Ato be the input array (zero-indexed) and B[i]to be the maximum sum over all sublists ending at, but not including position i(i.e. all sublists A[j:i]). Therefore, B[0] = 0, and B[1] = max(B[0]+A[0], 0), B[2] = max(B[1]+A[1], 0), B[3] = max(B[2]+A[2], 0), and so on. Then, clearly, the solution is given simply by max(B[0], ..., B[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])。
Since every Bvalue depends only on the previous B, we can avoid storing the whole Barray, thus giving us our O(1) space guarantee.
由于每个B值仅依赖于前一个B，我们可以避免存储整个B数组，从而为我们提供 O(1) 空间保证。
With this approach, msslreduces to a very simple loop:
使用这种方法，mssl简化为一个非常简单的循环：
def mssl(l):
best = cur = 0
for i in l:
cur = max(cur + i, 0)
best = max(best, cur)
return best
Demonstration:
示范：
>>> mssl([3,4,5])
12
>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5])
19
>>> mssl([-2,-3,-5])
0
If you want the start and end slice indices, too, you need to track a few more bits of information (note this is still O(1) space and O(n) time, it's just a bit hairier):
如果你也想要开始和结束切片索引，你需要跟踪更多的信息位（注意这仍然是 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
This returns a tuple (a, b, c)such that sum(l[a:b]) == cand cis maximal:
这将返回一个元组(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
回答by Faraz
This is the maximum sub-array problem. The Kadane's algorithm can solve it in O(n)time and O(1)space, and it goes as follows:
这就是最大子阵列问题。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
回答by Bhumik Thakkar
I am assuming that this is the question to find a sub-sequence in an array which produces the maximum sum. I encountered this problem while searching for a maximum sum SUBSET problem.
我假设这是在数组中找到产生最大总和的子序列的问题。我在搜索最大总和 SUBSET 问题时遇到了这个问题。
The java implementation for this question:
这个问题的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;
}
回答by Skagen
Here's an implementation in Java, using Kadane's Algorithm, which prints the indexes of the biggest sum. The implementation takes O(n) time and O(1) space.
这是 Java 中的一个实现，使用 Kadane 算法，它打印最大总和的索引。实现需要 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);
}
回答by PixelsTech
This postintroduces three ways to find the maximum subarray of an array.
这篇文章介绍了寻找数组最大子数组的三种方法。
- Brute force (O(n*n))
- Divide and conquer (O(nlgn))
- Kadane's algorithm (O(n))
- 蛮力 (O(n*n))
- 分而治之（O（nlgn））
- Kadane 算法 (O(n))
Among them, the fastest one is the Kadane's algorithm which has a time complexity of O(n).
其中，速度最快的是时间复杂度为O(n)的Kadane算法。
回答by redx21
if someone is looking for a longer version of a code, here it is:
如果有人正在寻找更长版本的代码，这里是：
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
