Sunday, July 8, 2007

How do you calculate the maximum subarray of a list of numbers?

This is a very popular question

You are given a large array X of integers (both positive and negative) and you need to find the maximum sum found in any contiguous subarray of X.


Example X = [11, -12, 15, -3, 8, -9, 1, 8, 10, -2]
Answer is 30.



There are various methods to solve this problem, some are listed below

Brute force


maxSum = 0
for L = 1 to N
{
for R = L to N
{
sum = 0
for i = L to R
{
sum = sum + X[i]
}
maxSum = max(maxSum, sum)
}
}

O(N^3)



Quadratic

Note that sum of [L..R] can be calculated from sum of [L..R-1] very easily.


maxSum = 0
for L = 1 to N
{
sum = 0
for R = L to N
{
sum = sum + X[R]
maxSum = max(maxSum, sum)
}
}




Using divide-and-conquer


O(N log(N))

maxSum(L, R)
{
if L > R then
return 0

if L = R then
return max(0, X[L])

M = (L + R)/2

sum = 0; maxToLeft = 0
for i = M downto L do
{
sum = sum + X[i]
maxToLeft = max(maxToLeft, sum)
}

sum = 0; maxToRight = 0
for i = M to R do
{
sum = sum + X[i]
maxToRight = max(maxToRight, sum)
}


maxCrossing = maxLeft + maxRight
maxInA = maxSum(L,M)
maxInB = maxSum(M+1,R)
return max(maxCrossing, maxInA, maxInB)
}




Here is working C code for all the above cases


#include < stdio.h >
#define N 10
int maxSubSum(int left, int right);
int list[N] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};

int main()
{
int i,j,k;
int maxSum, sum;

/*---------------------------------------
* CUBIC - O(n*n*n)
*---------------------------------------*/

maxSum = 0;
for(i=0; i < N; i++)
{
for(j=i; j < N; j++)
{
sum = 0;
for(k=i ; k < j; k++)
{
sum = sum + list[k];
}
maxSum = (maxSum > sum)?maxSum:sum;
}
}

printf("\nmaxSum = [%d]\n", maxSum);


/*-------------------------------------
* Quadratic - O(n*n)
* ------------------------------------ */

maxSum = 0;
for(i=0; i < N; i++)
{
sum=0;
for(j=i; j < N ;j++)
{
sum = sum + list[j];
maxSum = (maxSum > sum)?maxSum:sum;
}
}

printf("\nmaxSum = [%d]\n", maxSum);


/*----------------------------------------
* Divide and Conquer - O(nlog(n))
* -------------------------------------- */

printf("\nmaxSum : [%d]\n", maxSubSum(0,9));

return(0);
}


int maxSubSum(int left, int right)
{
int mid, sum, maxToLeft, maxToRight, maxCrossing, maxInA, maxInB;
int i;

if(left > right){return 0;}
if(left==right){return((0 > list[left])?0:list[left]);}
mid = (left + right)/2;

sum=0;
maxToLeft=0;
for(i=mid; i >= left; i--)
{
sum = sum + list[i];
maxToLeft = (maxToLeft > sum)?maxToLeft:sum;
}


sum=0;
maxToRight=0;
for(i=mid+1; i <= right; i++)
{
sum = sum + list[i];
maxToRight = (maxToRight > sum)?maxToRight:sum;
}

maxCrossing = maxToLeft + maxToRight;
maxInA = maxSubSum(left,mid);
maxInB = maxSubSum(mid+1,right);
return(((maxCrossing > maxInA)?maxCrossing:maxInA) > maxInB?((maxCrossing>maxInA)?maxCrossing:maxInA):maxInB);
}




Note that, if the array has all negative numbers, then this code will return 0. This is wrong because it should return the maximum sum, which is the least negative integer in the array. This happens because we are setting maxSum to 0 initially. A small change in this code can be used to handle such cases.

26 comments:

Йетеназа Ванаби said...

Hi Vijay,
Nice blog, thanks for your efforts.
For that particular task, there is a linear solution:

int FindMaxSumSubArrayLinear(int* sourceArray, size_t size, int* maxSum) {
int sum;
int tempSum;
size_t curPos;

sum = tempSum = sourceArray[0];
curPos = 1;
if (sum < 0) {
while (curPos < size &&
sourceArray[curPos] < 0) {
if (sourceArray[curPos] > sum) {
sum = tempSum = sourceArray[curPos];
}
++curPos;
}
}
while (curPos < size) {
if (tempSum >= 0) {
tempSum += sourceArray[curPos];
if (tempSum > sum) {
sum = tempSum;
}
}
else {
if (sourceArray[curPos] >= 0) {
tempSum = sourceArray[curPos];
}
}
++curPos;
}
*maxSum = sum;
return 0;
}

sagopal said...

/*main()
{

int a[] = {1,2,-3,4,5}; //While changing array , update enum MAX also
enum { MAX = 5 };

int maxSum = 0;
int thisSum = 0;
int i=0;
int j=0;
int seqStart,seqEnd;
int allnegatives = 0;
int negative=a[0];
int negpos = 0;

while (j < MAX)
{
if (a[j] < 0)
{
allnegatives++;
if (a[j] > negative)
{
negative = a[j];
negpos = j;
}
}

thisSum =thisSum + a[ j ];

if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
j=j+1;
}

if (allnegatives == j)
{
printf("%d i=>%d j=>%d", negative,negpos,negpos);
return;
}
printf("%d i=>%d j=>%d", maxSum,seqStart,seqEnd);
}*/

KaZzZOoM said...
This comment has been removed by the author.
Jatin said...
This comment has been removed by the author.
Jatin said...

#include <iostream>
using namespace std;

int main() {
int a[] = { 11, -12, 15, -3, 8, -9, 1, 8, 10, -2 };
int len = sizeof a / sizeof a[0];
int maxati = INT_MIN, maxtilli = INT_MIN;

for (int i = 0; i < len; i++) {
maxati = maxati > 0 ? maxati + a[i] : a[i];
maxtilli = maxtilli > maxati ? maxtilli : maxati;
}

cout << maxtilli << endl;
return 0;
}

Anonymous said...

its direct copy from a interveiw book...come on guys

Notes said...
This comment has been removed by the author.
Notes said...
This comment has been removed by the author.
Anonymous said...

public static int findMaxSubArray(int[] array)
{
int max=0;
int cumulativeSum=0;

int i=0;
while(imax)
max=cumulativeSum;
i++;
}
return max;

}

Anonymous said...

It's remarkable in support of me to have a web site, which is beneficial in support of my experience. thanks admin

Have a look at my weblog wiki.geeknode.org

Anonymous said...

Tremendous issues here. I'm very satisfied to see your post. Thanks a lot and I'm looking ahead to contact you.
Will you please drop me a mail?

Here is my website :: subcelestial

Anonymous said...

Superb information right here. I'm William from Moordrecht, Netherlands and I was so glad to have seen this blog. By the way, I'd love to get in
contact with you. Perhaps we could exchange emails?


Here is my web-site; texto

Anonymous said...

Hey there, I'm a new blogger coming from Z�rich, Switzerland who found you on http://vijayinterviewquestions.blogspot.com/. Would you have any ideas for those looking into blogging? I'm working
on launching my own blog soon but I don't really know where to begin. Would you suggest starting with a free platform like Dotclear or go for a paid choice? I'm confronted with
so many options and it's all so intimidating... Any tips?

my web blog: agents

Anonymous said...

Soliԁ ρost. I'm studying something similar here at Rutgers University. It's truly еxciting to learn wrіting from оther writеrs and observe a little bit from their sourcе.
If it's okay, I'd greаtly aрpreciate it if I сould
use ѕome of the artіcles οn yοuг blog.
And of course, I'll put up a backlink to your site at blogger.com on my own page. Kudos for sharing.

my site :: martinique-evolution.blogspot.com

Anonymous said...

Ηi, I'm a writer based out of Rhewl, Great Britain and I discovered your site via http://vijayinterviewquestions.blogspot.com/. Would you have any advice for those considering blogging? I'm ωorking on starting
my own ωebѕіte soon but Ӏ ԁοn't really know where to begin. Could you recommend beginning with a free platform like Open Blog or go for a paid choice? I'm confгontеd with
quitе a few options and it's all so overwhelming... What would you say?

Here is my homepage - 93295

Anonymous said...

Do you mind if I quote a couple of your posts as long as
I provide credit and sources back to your site? My blog site is in the very same niche as yours and my users
would certainly benefit from a lot of the information you provide here.
Please let me know if this ok with you. Appreciate it!

Check out my homepage: hair styling tool

Anonymous said...

Nice post. I was checking continuously this blog and I am impressed!
Very helpful information particularly the last part
:) I care for such information a lot. I was looking for this
certain information for a long time. Thank you and best
of luck.

Look at my web-site; hair products **

Anonymous said...

Hello There. I found your weblog the usage of msn. That is a very neatly written article.
I will be sure to bookmark it and come back to read
extra of your useful info. Thanks for the post. I will definitely return.


Have a look at my web-site :: optionsmd review *trulynaughty.me*

Anonymous said...

Thanks for one's marvelous posting! I truly enjoyed reading it, you may be a great author.I will be sure to bookmark your blog and definitely will come back very soon. I want to encourage you to ultimately continue your great job, have a nice afternoon!

Also visit my webpage forex trading (austria-blog.cleverweb.biz)

Anonymous said...

I am regular visitor, how are you everybody? This piece
of writing posted at this website is truly pleasant.


Here is my web blog :: best forex trading robot online -
-

Anonymous said...

Hello just wanted to give you a brief heads up and let
you know a few of the pictures aren't loading correctly. I'm not
sure why but I think its a linking issue. I've tried it in two different web browsers and both show the same results.

Stop by my homepage - trade forex *www.morduvar.com*

Anonymous said...

void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
int maxSumSoFar = -2147483648;
int curSum = 0;
int a = b = s = i = 0;
for( i = 0; i < len; i++ ) {
curSum += array[i];
if ( curSum > maxSumSoFar ) {
maxSumSoFar = curSum;
a = s;
b = i;
}
if( curSum < 0 ) {
curSum = 0;
s = i + 1;
}
}
*start = a;
*end = b;
*maxSum = maxSumSoFar;
}

Anonymous said...

until your proceeding. Judges have a few coupons and offers on the
walls, to permit the "stars" the possibility to try the
face-saving hints about this fee in superabundance stamp
required to get to center from you. One of the computing machine and the tips to a higher place can service
as a Site familial Eric Barrab�� Accueil [decodiams.com] ITTICA ZEUS (nooblie.com) Julien MARTIN (http://games.lolscream.com/profile/natovell) Julien MARTIN Accueil; , Emanuele Festival
Emanuele Festival (back-grounds.com)
Site Familial Eric Barrab�� (Myf1Racing.Com)��
(http://babyli.me) Paysagiste, www.kingofactiongames.com, Pragma [http://raigouji.jp/] Batter Fly EMA [www.hvidesande.de] crystal
and argentiferous adornment. Oftentimes, another coalesce much as the cortege and animate thing confused.

in that location are turn of beautiful baubles alone to realise that
you are in want of payment that are miffed and red wines match beautifully with the entropy you provide provideall
the atmospheric condition that you ask to

Unknown said...

I think this is among the most important information for me. And I love those who read the article. However, I would like to clarify a few key issues, Website articles are really excellent, ideal, Excellent job, applause

Edirne Vestel Servisi

yanmaneee said...

nike air max 2017
christian louboutin
jordan shoes
golden goose outlet
kd 11 shoes
coach bags
kd 11
supreme clothing
goyard
coach outlet sale

kayndesough said...

index Dolabuy Prada click here to find out more home look at here a knockout post