如何在O（n）中找到具有最大和的連續子陣列

Question

給定一個包含正數和負數的數列，問題是要找到一個具有最大總和和時間的連續子數組複雜度是O（n），例如，[1，-2,3,10，-4,7,2，-5]是一個數組，並且子數組[3，10，-4，7，2]有最大的總和是18. 那麼如何在O（n）中找到這個子數組？ Thx

Answer 1

Wiki link到此解決方案。它被稱爲最大子數組求和問題。解決方案由在O（n）時間運行的Kadane提供。

Answer 2

下面是Python中的解決方案。這個想法是搜索最大連續和。如果總和爲負值，則清空列表，如果不是負值，則必須保留這些元素。

l = [1,-2,3,10,-4,7,2,-5] 

def find_max(l): 
    s = 0 # Current sum 
    lsum = [] # Current subarray 
    res = (0, []) # Max value and subarray 

    for v in l: 
     s += v 
     lsum.append(v) 
     if s > res[0]: 
     res = (s, lsum[:]) 
     elif s < 0: 
     s = 0 
     lsum = [] 

    return res 

print find_max(l) 

結果：

(18, [3, 10, -4, 7, 2]) 

Answer 3

的想法是看累加系列（對待值的東西遞增/遞減），然後找到這個系列的低和高以後。

在僞碼：

sum = 0 
low = Integer.MaxValue 
highestSumSinceLow = Integer.MinValue 
For i = 0 to Array.Length-1 
    sum += Array[i]       // keep track of cumulative value since start 
    If sum < low Then       
    low = sum        // keep track of lowest sum since start so far 
    substart = i + 1       // and set substart to next value 
    sumsincelow = sum - low     // calculate sum from that low to here 
    If sumsincelow > highestSumSinceLow Then 
    highestSumSinceLow = sumsincelow   // keep track of highest sumsincelow 
    subend = i        // and set subend to this value 
Next i 

通過整個陣列去後，substart和subend點到子陣列的索引具有最高總和（這是highestSumSinceLow）。

這可能是最簡單和最有效的解決方案。它是O（n）並且不使用臨時數組。它從頭到尾只經過一次數組，並且記錄自開始以來的最低累積總數以及自該低數起的最高總和。