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

Advertisements

Written by fR0DDY

April 7, 2009 at 1:52 PM

One Response

Subscribe to comments with RSS.

  1. Thanks 🙂

    Cheema

    December 26, 2009 at 2:27 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: