#include<iostream.h>
#include<malloc.h>

int max(int a ,int b);
void print(int p[][3],int r,int c);
int returnMaxSum(int *a,int l);
int return2DMaxSum(int *a,int *b,int l);
int findMaxSumMatrix(int p[][3],int r,int c);

int main()
{

	int arr[3][3] = {{1,-2,3},{-4,5,6},{-7,-8,-9}};
	cout<<"Matrix Sum ... "<<endl;
	cout<<findMaxSumMatrix(arr,3,3)<<endl;
	return 0;
}

int returnMaxSum(int *a,int l)
{
	int maxend = 0;
	int maxsofar = 0;

	for(int i=0;i<l;i++)
	{
		maxsofar = max(maxsofar + a[i] ,0);
		maxend = max(maxsofar,maxend);
	}

	return maxend;
}


int return2DMaxSum(int *a,int *b,int l)
{
int *c ;
int max = -1;

c =(int *) malloc(sizeof(int) * l);

for(int i=0;i<l;i++)
	c[i] = b[i] - a[i];

max = returnMaxSum(c,l);
return max;

}

int findMaxSumMatrix(int p[][3],int r,int c)
{
	int max = -1,val;
	int temp[3],temp1[3];

	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c-1;j++)
			p[i][j+1] += p[i][j];
	}



	print(p,3,3);
	cin.get();

	for(i=0;i<c;i++)
	{
		for(int j=i;j<c;j++)
		{
			cout<<"Col 1: "<<i<<" Col 2: "<<j<<endl;
			if(i == j)
			{
				if(j != 0)
				{
				for(int k=0;k<r;k++)
					temp[k] = ( p[k][j] - p[k][j-1]);
				}
				else
				{
					for(int k=0;k<r;k++)
						temp[k] = p[k][j];
				}
				val = returnMaxSum(temp,r);
				if(val > max)
					max  =  val;
			}
			else
			{
				for(int k=0;k<r;k++)
					temp[k] = p[k][j];
				for(k=0;k<r;k++)
					temp1[k] = p[k][i];
				val = return2DMaxSum(temp,temp1,r);
				if(val > max)
					max  =  val;
			}
			cout<<"Temp : "<<val<<"  Max val :"<<max<<endl;
			cin.get();
		}
	}

	return max;

}


void print(int p[][3],int r,int c)
{

	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++)
			cout<<p[i][j]<<" ";
		cout<<endl;
	}
}

int max(int a ,int b)
{
	if( a> b)
		return a;
	return b;
}