Maximum Sum

The Problem

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

is in the lower-left-hand corner:

and has the sum of 15.

Input and Output

The input consists of an array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by integers separated by white-space (newlines and spaces). These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [-127, 127].

The output is the sum of the maximal sub-rectangle.

Sample Input

4
0 -2 -7  0 9  2 -6  2
-4  1 -4  1 -1
8  0 -2

Sample Output

15

// Maximum Sum.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
 
int A[100][100],m,n,maxsum,count=0,x,y,row,col;
int _tmain(int argc, _TCHAR* argv[])
{
      int i,j,r,c;
      void mat(int i,int j);
      printf("Enter the number of rows: ");
      scanf("%d",&m);
      printf("Enter the number of columns: ");
      scanf("%d",&n);
      //Taking the elements of the input matrix.
      for(i=0;i<m;i++)
      {
            for(j=0;j<n;j++)
            {
                  scanf("%d",&A[i][j]);
            }
      }
      //Printing the input matrix.
      printf("The matrix is:\n");
      for(i=0;i<m;i++)
      {
            for(j=0;j<n;j++)
            {
                  printf("%3d",A[i][j]);
            }
            printf("\n");
      }
//Forming possible row-column pairs or window sizes smaller than or equal to the dimensions of the original matrix.
      for(i=1;i<m+1;i++)
      {
            for(j=1;j<n+1;j++)
            {
                  mat(i,j);//Function for calculating the sum of the sub-matrices.
            }
      }
      //Printing the maximum sum sub-matrix and the maximum sum.
      printf("The maximum sum sub-matrix is:\n");
      for(m=x;m<row;m++)
      {
            for(n=y;n<col;n++)
            {
                  printf("%3d",A[m][n]);
            }
            printf("\n");
      }
      printf("The maximum sum is %d\n",maxsum);
      return 0;
}
void mat(int i,int j)
{
      int r,c,a,b,thissum=0;
for(r=0;r<=m-i;r++)//Defines the row position of the starting element of the sub-matrix.
      {
for(c=0;c<=n-j;c++)//Defines the column position of the starting element of the sub-matrix.
            {
                  thissum=0;
for(a=r;a<r+i;a++)//Defines the rows of elements to be included in the sub-matrix according to the window-size.
                  {
for(b=c;b<c+j;b++)//Defines the rows of elements to be included in the sub-matrix according to the window-size.
                        {
thissum=thissum+A[a][b];//Calculating the sub-sum.
                        }
                  }
                  count++;
                  if(count==1)
                  {
                        maxsum=thissum;
                        x=r;y=c;row=r+i;col=c+j;
                  }
                  else
                  {
                        if(thissum>maxsum)
                        {
                              maxsum=thissum;
x=r;y=c;row=r+i;col=c+j;//Storing the values the rows,columns,row and column of the starting element.
                        }
                  }
            }
      }
}
 
Enter the number of rows: 4
Enter the number of columns: 4
Enter the elements in the row-major order:
0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2

The matrix is:
  0 -2 -7  0
  9  2 -6  2
 -4  1 -4  1
 -1  8  0 -2

The maximum sum sub-matrix is:
  9  2
 -4  1
 -1  8

The maximum sum is 15
Press any key to continue . . .