如果我想計算具有最大總和的數組中的序列，則計算數組中具有最大總和的序列O（N）

Question

如何在具有O（n）時間複雜度的限制時執行此操作？

例如：{1,2,3,4，-3}的輸出將是4，因爲1 + 2 + 3 + 4的總和爲最大總和並且有4個數字在該序列

我知道如何做O（N^2）的時間複雜性，但不與O（N）的幫助？ :)

Answer 1

我想你可以遍歷這樣的：

MaxSum = 0; 
CurrentSum = 0; 
MaxLen = 0; 
CurrentLen = 0; 

Index = GetFirstPositiveValue(); 
// This function returns the first Index where Array[Index] > 0 
// O(n) 

while (Index < Array.Length()) { 
    // general loop to parse the whole array 
    while (Array[Index] > 0 && Index < Array.Length()) { 
     CurrentSum += Array[Index]; 
     CurrentLen++; 
     Index++ 
    } 
    // We computed a sum of positive integer, we store the values 
    // if it is higher than the current max 
    if (CurrentSum > MaxSum) { 
     MaxSum = CurrentSum; 
     MaxLen = CurrentLen; 
    } 
    // We reset the current values only if we get to a negative sum 
    while (Array[Index] < 0 && Index < Array.Length()) { 
     CurrentSum += Array[Index]; 
     CurrentLen++; 
     Index++; 
    } 
    //We encountered a positive value. We check if we need to reset the current sum 
    if (CurrentSum < 0) { 
     CurrentSum = 0; 
     CurrentLen = 0; 
    } 
} 
// At this point, MaxLen is what you want, and we only went through 
// the array once in the while loop. 

啓動第一個積極的元素。如果每個元素都是負數，那麼選擇最高，問題就結束了，這是一個1元素序列。

只要我們有正值，我們就繼續求和，所以我們有一個當前的最大值。當我們有否定的時候，我們檢查當前的最大值是否高於存儲的最大值。如果是這樣，我們用新值替換存儲的最大值和序列長度。

現在，我們總結負數。當我們發現另一個肯定的時候，我們必須檢查一下：

如果當前總和是正數，那麼我們仍然可以得到這個序列的最大和。如果它是負值，那麼我們可以拋出當前總和，因爲最大總和不包含它：

在{1，-2,3,4}中，3 + 4大於1-2 + 3 +4

只要我們還沒有經過整個陣列，我們就重新啓動這個過程。當我們有一個子序列產生負和時，我們只重置序列，並且只有當我們有更大的值時，我們才存儲最大值。

我認爲這是按照預期工作的，我們只通過一次或兩次數組。所以這是O（n）

我希望這是可以理解的，我很難讓我的想法清楚。使用{1,2,3，-4,5}/{1,2,3，-50,5}/{1,2,3，-50,4,5}等小例子執行此算法可能會有所幫助如果我不太清楚:)

Answer 2

如果你知道子數組的長度爲N的數組的末尾的最高金額，你可以平凡計算它的長度爲N +一個1：

[..., X]  has max subsum S 
[..., X, Y] has max subsum max(0, S + Y) 

因爲您包含Y或者您有一個空子數組（因爲子數組在列表的末尾）。

你可以找到所有款項的最高限額由來自空單建立這個在任何位置結束子陣：

[]    S = 0 
[1]   S = 1 
[1, 2]   S = 3 
[1, 2, -4]  S = 0 
[1, 2, -4, 5] S = 5 

你那麼只需要跟蹤的最大和寬度。這裏有一些演示算法的Python代碼。

def ranges(values): 
    width = cum_sum = 0 

    for value in values: 
     cum_sum += value 
     width += 1 

     if cum_sum < 0: 
      width = cum_sum = 0 

     yield (cum_sum, width) 

total, width = max(ranges([-2, 1, 2, 3, -8, 4, -3])) 

total, width 
#>>> (6, 3)