How to find the maximum contiguous SUM in an array (which contains positive and negative numbers)?

Question

I want to write a function ContigSum(i,j) that calculates the sum of the contiguous elements a[i] through a[j], where i<=j and a[] contains positive and negative numbers.

Could you please tell me a time efficient solution to find maximized contiguous SUM in the array?

Answer 1

This is discussed in Column 7 of the 1st Edition or Column 8 of the 2nd Edition of 'Programming Pearls' by Jon Bentley.

Answer 2

Well explained in the wikipedia entry about the subject. I find the Python code (i.e., executable pseudocode) they give for Kandane's Algorithm to be a little gem:

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