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(n^{3}). 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

### Like this:

Like Loading...

*Related*

AbhiThis is great catch. Thanks for the patch. God bless Bentley

hp7500In 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() ;

recursiveWhy is a zero length sub-array not considered a sub-array?

wuhrrPost authorDear recursive,

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

sadint 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;

}

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);

}

JackI 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.

ManaviWhy 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..??

ManaviI am so sorry…i missed the most integral part of the question..the ordering..

PhucThe problem with negative-only arrays is because you started with

maxSoFar = maxUpToHere = 0

they should be assigned to -inf (negative infinity).

IanPhuc 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.

HaiPost authorRight on, Phuc & Ian

AlexI 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;

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

Now he has to consider my simplified answer.

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?

HaiPost author@Fang: I don’t know (yet).

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;

}

kbthe above given solution has complexity of O(N).

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;

}

napsterpublic 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;

}

napsterthis website is bullshit, it prints half of my solution

acharya.ash@gmail.comDoesnt work for -1,2,3,-4 ?

HaiPost author@acharya.ash: why don’t you find out?

HenrikWhat is the name of this algorithm?

HaiPost author@Henrik: I don’t know the name of the algorithm. Sorry about that.

JJIts called Kadane’s algorithm

HaiPost authorThank you JJ. The algorithm now has a name.