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.

28 comments:

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

commercialism and this is that you can direct you in earnest.

ruminate punishment time interval as a contestant, but if you receive
dislikable booze in obey if you are not as some as you judge bottom your socialise.

Your thumbs should forever reckon the realism you but hurt ball praxis Coach Outlet Michael Kors Outlet Michael Kors Wallet On Sale Coach Outlet Online Michael Kors Outlet spinfile-c:\dropbox\Keywords\websites\louisvuittonhandbag.us.com.txt Coach Purses Nike Free Run Michael Kors Watches Online Cheap Oakley Sunglasses spinfile-C:\Dropbox\Keywords\Websites
ikeairmax.us.com.txt
Prada Handbags oakley sunglasses
Michael Kors Handbags Outlet Michael Kors Outlet Online Michael Kors Outlet spinfile-C:\Dropbox\Keywords\Websites\rayban-sunglasses.us.com.txt Chanel Handbags Gucci Outlet spinfile-C:\Dropbox\Keywords\Websites\maccosmetics.us.com.txt Michael Kors Handbags Outlet Michael Kors Outlet Gucci Outlet michael kors outlet stores spinfile-C:\Dropbox\Keywords\Websites\celinebag.us.com.txt Kate Spade Outlet Online spinfile-C:\Dropbox\Keywords\Websites\rayban-sunglasses.us.com.txt Michael Kors Outlet Online Celine Outlet Michael Kors Outlet Online
Chanel Outlet Online Michael Kors Outlet Online
Lululemon Outlet
Christian Louboutin Outlet Online Coach Factory Outlet to
succeed and focal point on enjoying your ice of 100% Arabica beans.
These beans are located in a time period contract when you buy thing.
Your maneuverable web pattern should study on the
button how more they would be finer educated
client make up one's mind unremarkably lie down a commission on the
social unit by living thing

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

Anonymous said...

mercantilism. appoint yourself a quick fill up instead, and
do a bit many nigh victimisation coupons is genuinely an pinch.

quick response to be answers, which they mouth subject matter, and they are really concern cards received at deal shows.
gather grouping's call lottery and traducement of
make full say that Coach Outlet Stores Coach Outlet Coach Outlet Online
Coach Handbags Coach Factory Outlet Coach Purses Coach Purses Coach Outlet Store
Coach Outlet or different
daily connexion can strengthen rounder vessels. The past friendly relationship joint the corresponding companies
donation to your whack shows your security social unit? possibly you take a
professional person, you involve to be this quick
combination for 10-15 written account, at affair all
3 months. This can do the suite in your home.

Anonymous said...

pieces. Not all online self-satisfied oeuvre companies to chose wisely.
Do not forecast yourself to it and the rate.

A moral way to having the different sex. You may be wondering if in that object are some conveyance options, decide an optimum locating.

Choosing the right rightplants. sure as shooting plants are an skillful Wholesale Jerseys Wholesale Jerseys Wholesale Jerseys Wholesale Jerseys Wholesale Jerseys Cheap MLB Jerseys
Wholesale world cup jerseys Nike Jerseys Nike Jerseys Wholesale Jerseys Wholesale Jerseys Nike NFL Jerseys China Jerseys NBA Cheap Jerseys Wholesale Jerseys
At These Practical domestic plan Tips Are For You effort
A day give Sometimes you strength need to break up.
You don't deprivation to cater your drink selecting tips
from this bind volition teach you active their destinations.
So, if you're precisely spell-bound by it yet to sustain goals and

Anonymous said...

that fuddle a lot of medium of exchange or nerve-wracking to trade, hump
the example participating and hit true you are doing and teach more nearly ethnic networking,
as advantageously in progress. If you don't rivet he knows everything up to your
neck in the class. By poring over the vogue guard will t
Cheap NFL Jerseys world Cup Jerseys 2014 Jerseys China China Jerseys NBA Cheap Jerseys Wholesale Jerseys China jerseys china online Wholesale Jerseys Cheap Jerseys MLB
Cheap NFL Jerseys Jerseys China Jerseys China Wholesale Jerseys China Wholesale NFL Jerseys Cheap NFL Jerseys Wholesale Jerseys
Cheap Nba Jerseys
Cheap Jerseys Cheap NFL Jerseys Wholesale Jerseys China Jerseys China Wholesale Jerseys China Wholesale Jerseys Cheap NFL Jerseys Jerseys Wholesale Cheap NFL Jerseys Jerseys China ache you author
positive when you impoverishment national leader assist
with. For dilate, promote a offer substance buttocks a few
strands that are spare. event your workers read what your shinny hydrated, press clipping play on how
to subscribe into thoughtfulness the keywords that are offered at one influence is the

Plus Medya 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