最大總和子列表？

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