Largest Sum Submatrix (2D subarray)

Given a matrix M with (with positive or negative numbers) find the largest sum S of any sub-matrix of M.

public static int maxSumSubMatrix(int[][] M)
{
	int rows = M.length;
	int cols = M[0].length;
	int maxLeftCol = 0;
	int maxRightCol = 0;
	int maxTopRow = 0; int top = 0;
	int maxBottomRow = 0; int bottom = 0;
	int maxsum = MIN_INTEGR;
	
	//select a left column
	for(int left=0; left<cols; left++)
	{
		//select a right column for each of the left column
		for(int right=left; right<cols; right++)
		{
int[] temp = new int[rows];
			//let’s combine data between left and right into a single aray o run Kadane on it
			for(int i=0;i<rows;i++)
				temp[i] += M[i][right];
			int sum = maxSumSubArray(temp, top, bottom);
			if(sum > maxsum)
			{
				maxsum = sum;
				maxLeft = left;
				maxRight = right;
				maxTop = top;
				maxBottom = bottom;
			}
		}
	}
	returm maxSum;
}

Leave a Reply

Your email address will not be published. Required fields are marked *