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]

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)

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

/*-------------------------------------
* ------------------------------------ */

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.

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