CareerCup

#include<stdio.h>
#include<conio.h>



int main()
{
    int i,j,max=0,n,k,sum=0;
    scanf("%d",&n);
    int M[n][n],S[n][n],RS[n][n],CS[n][n],;
	for(i=0;i<=n;i++)
	{
		M[i][0]=M[0][i]=S[i][0]=S[0][i]=RS[i][0]=RS[0][i]=CS[i][0]=CS[0][i]=0;    

	}
               //this is to check boundary condition


	for(i=1;i<=n;i++)
         {
                     
                    for(j=1;j<=n;j++)
                    {
				    
                                    scanf("%d",&M[i][j]);
                                    RS[i][j]=RS[i][j-1]+M[i][j];
				    CS[i][j]=CS[i-1][j]+M[i][j];
				    S[i][j]=S[i-1][j-1]+RS[i][j]+CS[i][j]-M[i][j];
                    }  
         }
    
    scanf("%d",&k);
    
		//taken the size of sub matrix

	for(i=k;i<=n;i++)
       {
		for(j=k;j<=n;j++)
			{
				sum=S[i][j]-S[i-k][j]-S[i][j-k]+S[i-k][j-k];
				if(sum>max)
				max=sum;	
			}
	}
     

	printf("%d\n",sum); 
                               
                                
     getch();
     return 0;
}

Here is my solution. It is inspired by the classic problem of finding max subarray in 1D array. Here the program tries to find a max submatrix which ends at {i,j}. Then the max submatrix should be the maximum among the max submarices ending at all i's and j's.

To search {i,j} start at j=0, for each i, it needs O(n) to find a max submatrix for each {i,j},
for j>0, the results from j-1 can be used which is basically in a DP way.

Overall complexity should be O(n^3)

#include<stdlib.h>
#include<stdio.h>
#define N 9
#define AT(a,b,c) (*((a)+(b)*N+(c)))
void findMaxEnd(int *a,
                int *max,int *max_i, int *max_end,
		int i,int j,
		int *maxe, int *max_height, int *max_posi)
{
  int height;
  int pos=i;
  int hi;
  int s=0;
  *maxe=-999999;
  for (hi=i;hi>=0;hi--)
  {
   s+=AT(a,hi,j);
   AT(max_end, pos, i-hi)+=s;
   if (s>AT(max_end, pos, i-hi))
   {
     AT(max_end, pos, i-hi)=s;
     AT(max_i,pos,i-hi)=j;
   }
   if (*maxe<AT(max_end,pos,i-hi))
   {
     *maxe=AT(max_end,pos,i-hi);
     *max_height = i-hi;
     *max_posi = AT(max_i,pos,i-hi);
   }

  }

}

int main()
{
int a_0[N*N]={
10,10,1 ,23,-4, 5, 6,23, 7,
-6,10,12,3 ,-4, 5,-3,10, 7,
10,10,-200,23,-4,-200, 6,23,-7,
-2, 3,1 ,99,99, 5,32, 0,-7,
10, 4,1 ,99,99, 5, 6,-5,-7,
3 , 5,1 ,99,99,-5,-3,-5, 7,
18,-6,1 ,23,-4,-200, 6,4 , 7,
2 ,10,1 ,-2,14, 5,10,10, 7,
2 ,10,1 ,23,-4, 5, 2,2 , 7
};
int s_0[N];
int max_0[N*N], max_i0[N*N], max_end0[N*N];
int *a=a_0,*s=s_0,*max=max_0,
    *max_i=max_i0,*max_end=max_end0;
int maxe,max_height,max_posi;
int all_maxe=-999999, all_max_height, all_max_posi,
    all_i=-1, all_j=-1;
int i,j;

for (i=0;i<N;i++)
 for (j=0;j<N;j++) 
  {
    AT(max_end,i,j)=-999999;
    AT(max_i,i,j) = 0;
  }

for (j=0;j<N;j++)
 for (i=N-1;i>=0;i--)
 {
  findMaxEnd(a,max,max_i,max_end,i,j,&maxe,&max_height,&max_posi);
  printf("%d %d %d %d %d\n",j,i,maxe,max_height,max_posi);
  if (all_maxe<maxe)
  {
    all_maxe=maxe;
    all_max_height=max_height;
    all_max_posi=max_posi;
    all_i=i;
    all_j=j;
  }
 }
printf("Max submatrice:\n");
for (i=all_i-all_max_height;i<=all_i;i++)
{
  for (j=all_max_posi;j<=all_j;j++)
  printf("%5d",AT(a,i,j));
  printf("\n");
}

return 0;
}