Find Largest Sum of Contiguous Numbers in an Array

This is one popular interview question. The problem: given an array which could contain zero, negative, and positive numbers, find the largest sum of contiguous sub-array. For example, if the array contains:

    31, -41, 59, 26, -53, 58, 97, -93, -23, 84
		

then the largest sum is 187 taken from the [59 .. 97] block

My research points to Jon Bentley’s solution as the most efficient solution (see his book, “Programming Pearls”). In fact, Bentley was probably the person who started this thread. His solution has a complexity of O(n) which is very good, considering the brute force solution is of O(n3). Here is a Python implementation of Bentley’s solution:

def largest(array):
    maxSoFar = maxUpToHere = 0

    for element in array:
        maxUpToHere= max(maxUpToHere + element, 0)
        maxSoFar = max(maxSoFar, maxUpToHere)


    return maxSoFar

This solution is very efficient, short, and easy to remember. To understand it, I recommend reading his book, “Programming Pearls.”

After implementing this solution, I wrote some test cases to verify its correctness. Overall, the code works well, but it does not return the correct value for cases when the whole array contains only negative numbers. For example, consider this array:

    -3, -1, -2

I expect to see -1 as the largest sum, but instead, I got 0. After studying the algorithm, I noticed that the problem comes from the line:

    maxUpToHere= max(maxUpToHere + element, 0)

For negatives-only cases, maxUpToHere will be zero because it is the larger of the two. Instead of zero, the correct output in these cases should be the largest number in the array. I also noticed that negatives-only are the only cases which cause trouble, so we can add detection to the code and return the largest element instead of maxSoFar. Here is the patched code:

# This is based on Bentley’s Programming Pearls
# My (Hai Vu’s) modification: if the array is all negatives
# then max is the largest element
def largest(array):
    maxSoFar = maxUpToHere = 0
    largestElement = array[0]
    allNegatives = True
    for element in array:
        maxUpToHere= max(maxUpToHere + element, 0)
        maxSoFar = max(maxSoFar, maxUpToHere)
        largestElement = max(largestElement, element)
        if element >= 0:
            allNegatives = False
    if allNegatives:
        return largestElement
    return maxSoFar

The patched code works well for all cases. However, if you have a better solution, I would like to learn about it. My python program is available for download: largestsumpy.pdf

27 thoughts on “Find Largest Sum of Contiguous Numbers in an Array

  1. hp7500

    In C#.net (with finding the first and last elements of the array)

    int[] i = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
    int maxSoFar = 0;
    int maxUpToHere = 0;

    int itr = 0;
    int startIndex = 0;
    int endIndex = 0;

    int countStart = -1;

    foreach (int n in i)
    {
    //maxUpToHere = (maxUpToHere + n > 0 ? maxUpToHere + n : 0);
    //maxSoFar = (maxSoFar > maxUpToHere ? maxSoFar : maxUpToHere);

    if ((maxUpToHere + n) > 0)
    {
    maxUpToHere += n;
    countStart++;
    }
    else
    {
    maxUpToHere = 0;
    countStart = -1;
    }

    if (countStart == 0)
    {
    startIndex = itr;
    }

    if (maxSoFar < maxUpToHere)
    {
    maxSoFar = maxUpToHere;
    endIndex = itr;
    }

    itr++;
    }

    this.richTextBox1.Text = “Max so far: ” + maxSoFar.ToString() + “\nStartIndex: ” + startIndex.ToString()+”\nEndIndex: “+ endIndex.ToString() ;

  2. wuhrr Post author

    Dear recursive,
    If we take zero-length sub-array, then Bentley’s original solution is correct, even for negative-only cases.

  3. sad

    int FindMaxSumSubArray(int* data, int length)
    {
    int max = 0;
    int sum = 0;

    for(int i=length-1; i>=0; i–)
    {
    sum += data[i];

    if(sum max)
    {
    max = sum;
    }
    }

    // all negative
    if(max == 0)
    {
    max = data[0];
    for(int i=1; i max) max = data[i];
    }
    }

    return max;
    }

  4. amateurcoder

    #include
    #include
    //Program to print the largest subarray sum and the indexes of the subarray
    void main()
    {
    int maxuptohere=0,maxsofar=0,arr[5]={84,20,-50,-50,-60};
    clrscr();
    int allneg=1,maxelem=arr[0],start=-1,end=-1,indx=0;
    for(int i=0;i=0?(start=(start==-1)?i:start),maxuptohere+arr[i]:0;
    maxsofar=maxuptohere>=maxsofar?(end=i),(start=(maxuptohere==arr[i])?i:start),maxuptohere:maxsofar;
    maxelem=maxelem>arr[i]?indx=i,arr[i]:maxelem;
    if(arr[i]>=0)
    allneg=0;
    }
    if(allneg)
    start=end=indx;
    printf(“Ans: %d %d %d”,allneg==1?maxelem:maxsofar,start,end);
    }

  5. Jack

    I really like this solution, but just to be picky, there’s no need to maintain an allNegatives variable. Just check to see if the largestElement is negative after iterating through the list. No biggie, but does eliminate n comparisons.

  6. Manavi

    Why don’t we sort the array and find the index of the frst positive number in it and after that number all the array elements would be a part of the subarray..
    and in case of an all negative array just the last element (the greatest) can be the subarray..??

  7. Phuc

    The problem with negative-only arrays is because you started with
    maxSoFar = maxUpToHere = 0
    they should be assigned to -inf (negative infinity).

  8. Ian

    Phuc hit it on the head.

    The alg could first loop through the array to find the smallest object and assign this instead of -inf.

    This will not hurt the O(n) runtime.

  9. Alex

    I think this may be cleanner, instead of keeping track on wheter the content has negatives:

    int tmpMax = 0; // start the counter at 0
    int max = array[0]; // the 1st maximum is the 1st element. This saves us of potential all negative values.
    for(int val: array){
    tmpMax = Math.max(tmpMax+val, val); //Keep adding or get current if higher
    max = Math.max(tmpMax, max); // keep track on max value
    }
    return max;

  10. Speedo

    Thanks for the answers, to my 5th grade grandsons question – “What is a contiguous Number?”

    Now he has to consider my simplified answer.

  11. Fang (@___dev)

    Hi I was curious about real world applications for this algorithms and was not able to find any results on Google. What actually does this algorithm serve to do?

  12. kb

    #include

    int main()
    {
    int a[7]={-1,-3,-4,-5,6,-7,-8},i=0;
    int startInd = 0, endInd = 0, sum = 0, finalSum=0, finalStartInd=0, finalEndInd=0;
    for(i=0; i 0)
    {
    sum += a[i];
    endInd = i;
    }
    else
    {
    if(finalSum < sum)
    {
    finalSum = sum;
    finalStartInd = startInd;
    finalEndInd = endInd;
    }

    if(i+1<7)
    startInd = i+1;
    sum = 0;
    }
    if(finalSum < sum)
    {
    finalSum = sum;
    finalStartInd = startInd;
    finalEndInd = endInd;
    }
    }
    printf("\n\nResult:start Ind %d endInd %d Sum %d",finalStartInd,finalEndInd,finalSum);
    return 0;
    }

  13. Amit Veerani

    //above problem seems to be complex
    // try this one
    //Time complexity O(n)

    public static int findMaxSubArray(int[] array)
    {
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
    while(i<array.length)
    {
    if(cumulativeSum+array[i]max)
    {
    max=cumulativeSum;
    savepoint=start;
    end=i;
    }
    i++;
    }

    System.out.println(“Max : “+max+” Start indices : “+savepoint+” end indices : “+end);
    return max;

    }

  14. napster

    public static int findMaxSubArray(int[] array)
    {
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
    while(i<array.length)
    {
    if(cumulativeSum+array[i]max)
    {
    max=cumulativeSum;
    savepoint=start;
    end=i;
    }
    i++;
    }

    System.out.println(“Max : “+max+” Start indices : “+savepoint+” end indices : “+end);
    return max;

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s