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

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(*n*^{6}) time. The trivial solution to it would take O(*n*^{4}) 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(*n*^{3}) solution for it too. In this algorithm we calculate the prefix sum for all possible row combination in O(*n*^{2}) and then take out their maximum contigous sum in O(n) time. Thus doing the task in O(*n*^{3}) 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

Thanks 🙂

CheemaDecember 26, 2009 at 2:27 PM