# COME ON CODE ON

A blog about programming and more programming.

## Maximum Subarray in 1-D and 2-D Array

with one comment

This is a well known problem wherein we have to find the subarray whose sum is maximum. For 1-D array the fastest time that this can be done is in O(n). The algorithm was given by by Jay Kadane of Carnegie-Mellon University. It can be found here.
Its C++ implementation would look like this.

```int MaxSum1D(vector M)
{
int N=M.size(),i,t=0,S=1<<31;
for (i=0;i<N;i++)
{
t=t+M[i];
S=max(t,S);
if (t<0)
t=0;
}
return S;
}```

For finding the maximum subarray in a 2-D array the brute force method would take O(n6) time. The trivial solution to it would take O(n4) time which should be good enough for most questions on online judges. Its C++ implementation would be:

```int main()
{
int N,maxsum=1<<31,i,j,k,l,m,sum,p;
scanf("%d",&N);
vector< vector > M(N+1,vector(N+1,0));
vector< vector > S(N+1,vector(N+1,0));
for (i=1;i<N+1;i++)
for (j=1;j<N+1;j++)
scanf("%d",&M[i][j]);

for (i=1;i<N+1;i++)
for (j=1;j<N+1;j++)
S[i][j]=M[i][j]+
S[i-1][j]+S[i][j-1]-S[i-1][j-1];

maxsum=-128;
for (i=1;i<N+1;i++)
for (j=1;j<N+1;j++)
for (k=i;k<N+1;k++)
for (l=j;lmaxsum)
maxsum=sum;
}
printf("%d\n",maxsum);
}```

But kadane gave a O(n3) solution for it too. In this algorithm we calculate the prefix sum for all possible row combination in O(n2) and then take out their maximum contigous sum in O(n) time. Thus doing the task in O(n3) time. C++ implementation would be :

```int MaxSum2D(vector< vector > M)
{
int S=1<<31,k,j,i,t,s;
int N=M.size();

for (i=0;i<N;i++)
{
vector pr(N,0);
for (j=i;j<N;j++)
{
t=0;s=1<<31;
for (k=0;k<N;k++)
{
pr[k]=pr[k]+M[j][k];
t=t+pr[k];
s=max(t,s);
if (t<0)
t=0;
}
S=max(S,s);
}
}
return S;
}```

For finding the minimum and the position of the subarrays slight changes need to be made to the codes.

-fR0D

Written by fR0DDY

April 7, 2009 at 1:52 PM