最大总和子列表？

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

它要求您选择列表的小款，使得小该款的总和是最大的。

如果该列表是与最大的一笔一切积极[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

Answer 2

所以，如果你了解一个子表是什么（或片，它可以被假定为同样的事情），切片由开始索引定义和结束指数。

所以，也许你可以尝试迭代所有可能的开始和结束索引并计算相应的总和，然后返回最大值。

提示：起始索引可以在0到len(given_list)-1之间变化。结束索引可以从start_index到len(given_list)-1。您可以使用嵌套for循环来检查所有可能的组合。

Answer 3

简单的解决方案是遍历列表，只是尝试添加切片，直到找到最好的切片。这里我还包括了返回实际子列表的选项，默认情况下这是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)) 

Answer 4

这种区别可能不是到OP，谁似乎只是想了解如何在所有解决这个问题很重要，但我认为值得一提的是：

这里的其他解决方案包括反复总结列表的所有子部分。我们可以通过使用动态编程来避免这些重复的总和，因为当然，如果我们已经知道从i到j之间的总和，我们不需要再次叠加它们以获得从i到j+1的总和！

也就是说，做出部分和的2d数组，这样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）Lev/Inbar方法的时间和O（1）内存（如果没有像Inbar的第一个代码示例一样实现的话）。

Answer 5

实际上有一个非常优雅，非常有效的解决方案，使用动态编程。这需要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 6

这是the maximum sub-array problem。该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 7

我假设，这是产生最大金额的数组找到一个子序列的问题。我在搜索最大总和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; 
} 

Answer 8

以下是一个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); 
} 

Answer 9

这post介绍了三种方法来找到一个数组的最大子阵列。

• 蛮力（O（N * N））
• 分而治之（O（nlgn））
• Kadane的算法（O（n））的

其中，速度最快一个是具有O（n）时间复杂度的Kadane算法。

Answer 10

如果有人正在寻找的代码更长的版本，那就是：

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 

Answer 11

根据问题的情况下，如果在列表中的所有元素都是负面的，它应该返回最大总和为“零”

，而不是如果你想输出作为最大的子数组（中负数），则下面的代码将有助于：

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