如何在數組中找到最大連續SUM（包含正數和負數）？

Question

我想寫一個函數ContigSum(i,j)，它計算連續元素a[i]到a[j]的總和，其中i<=j和a[]包含正數和負數。

您能否告訴我一個有效的解決方案，以便在數組中找到最大化的連續SUM？

Answer 1

在wikipedia entry中對此進行了很好的解釋。我發現Python代碼（即，可執行的僞代碼），他們給了Kandane的算法是一個小寶石：

def max_subarray(A): 
    max_so_far = max_ending_here = 0 
    for x in A: 
     max_ending_here = max(0, max_ending_here + x) 
     max_so_far = max(max_so_far, max_ending_here) 
    return max_so_far 

Answer 2

這在Jon Bentley的'Programming Pearls'的第二版的第1版或第8欄的第7欄中進行了討論。

Answer 3

亞歷克斯，你有一個非常優雅的算法，但它需要修正包含單個元素的數組是負面的。

當然，在Kadane的原始算法中，可以獲得對於瞭解「路徑」有用的子數組開始和結束索引。

這裏有一個不雅的，但我認爲正確的Python功能：

def max_subarray(A): 
    (maxSum, maxStartIndex, maxEndIndex) = (float("-inf"), 0, 0) 
    (currentMaxSum,currentStartIndex,currentEndIndex) = (0,0,0) 

    for item in A: 
     currentMaxSum = currentMaxSum + item 
     if currentMaxSum > maxSum : 
      (maxSum, maxStartIndex, maxEndIndex) = (currentMaxSum, currentStartIndex, currentEndIndex) 
     if currentMaxSum < 0 : 
      currentMaxSum = 0 
      currentStartIndex = currentEndIndex + 1 

     # continue here. 
     currentEndIndex = currentEndIndex + 1 

    return (maxSum, maxStartIndex, maxEndIndex) 

Answer 4

static void MaxContiguousSum(int[] x, int lb, int[] result) 
{ 
    int start, end, sum, testSum; 

    start = lb; 
    end = lb; 

    /* Empty vector has 0 sum*/ 
    sum = 0; 

    testSum = 0; 
    for (int i=lb; i < x.length; i++) 
    { 
     if (sum + x[i] < 0) 
     { 
      /* Net contribution by current term is negative. So, contiguous sum lies in [start,i-1] 
       or [i+1, array upper bound]*/ 
      MaxContiguousSum(x, i+1, result); 

      if (result[0] < sum) 
      { 
       result[0] = sum; 
       result[1] = start; 
       result[2] = end; 
      } 
      return; 

     } 
     else 
     { 
      testSum += x[i]; 

      if (testSum > 0) 
      { 
       /* Move the end marker since incrementing range is beneficial. */ 
       end = i; 

       /* update the sum*/ 
       sum += testSum; 

       /* reset the testSum */ 
       testSum = 0; 
      } 
     } 

    } 

    /* Update the results */ 
    result[0] = sum; 
    result[1] = start; 
    result[2] = end; 

    return; 


} 

Answer 5

這是正確的Java代碼，它將處理方案，包括所有的負數。

public static long[] leftToISumMaximize(int N, long[] D) { 
     long[] result = new long[N]; 
     result[0] = D[0]; 
     long currMax = D[0]; 
     for (int i = 1; i < N; i++) { 
      currMax = Math.max(D[i], currMax + D[i]); 
      result[i] = Math.max(result[i - 1], currMax); 
     } 
     return result; 
    } 

Answer 6

這裏是C++代碼I只是實現和測試上的Visual Studio 2012

int maxSum(int *A, int lo, int hi) { 
    int left = lo, right = lo, sum = INT_MIN, currentMaxSum = 0, maxLeft = lo, maxRight = lo; 
    for(int i = lo; i < hi; i++) { 
     currentMaxSum += A[i]; 
     if(currentMaxSum > sum) { 
      sum = currentMaxSum; 
      right = i; 
      maxLeft = left; 
      maxRight = right; 
     } 
     if(currentMaxSum < 0) { 
      left = i+1; 
      right = left; 
      currentMaxSum = 0; 
     } 
    } 
    printf("Maximum sum contiguous subarray :"); 
    for(int i = maxLeft; i <= maxRight; i++) 
     printf(" %d", A[i]); 
    printf("\n"); 
    return sum; 
} 

下面是主（）代碼來調用上述功能。

int main() { 
    int A[] = {3,-4, -3, 2, 6}; 
    int N = sizeof(A)/sizeof(int); 

    printf("Maximum sum : %d\n", maxSum(A, 0, N)); 

    return 0; 
} 

Answer 7

這是我在Ruby中的解決方案。返回O（n）時間和O（1）存儲器中的最大連續子流。我也寫了一些單元測試，以防萬一;）

def largest_contiguous_subsum(array) 
    max_sum = 0 
    current_sum = 0 
    array.each do |num| 
    current_sum += num 
    max_sum = current_sum if current_sum >= max_sum 
    current_sum = 0 if current_sum < 0 
    end 

    return max_sum 
end