Max submatrix sum in a matrix

Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.

Thoughts:
Go through each submatrix (O(n^4) of them) and compute their sums, keeping track of the curren maximum. Without additional optimization, the computation of sums cost O(n^4), giving total a O(n^6) algorithm. We can precompute some sums to reduce the total costs to O(n^4):
Let’s say we need to compute the sum of the submatrix (startRow, startCol) -> (endRow, endCol), S. We can first pre-compute the sum of (0,0) -> (endRow, endCol) denote as S_{1}, the sum of (0,0) -> (endRow, startCol-1) denote as S_{2}, the sum of (0,0) -> (startRow-1, endCol) denote as S_{3} and the sum of (0,0) -> (startRow-1, startCol-1) denote as S_{4}, then S = S_{1} - S{2} - S{3} + S{4}. Hence, we can pre-compute sums of (0,0) -> (i,j) for every pair of (i,j). Then we searching, the computation of sum of submatrix will only need a single operation.

Codes:

	private static int[][] sums;

	private static void preComputeSums(int[][] matrix) {
		sums = new int[matrix.length][matrix[0].length];
		for (int i = 0; i < matrix.length; ++i) {
			for (int j = 0; j < matrix[i].length; ++j) {
				if (i == 0 && j == 0)
					sums[i][j] = matrix[i][j];
				else if (j == 0)
					sums[i][j] = sums[i - 1][j] + matrix[i][j];
				else if (i == 0)
					sums[i][j] = sums[i][j - 1] + matrix[i][j];
				else
					sums[i][j] = sums[i - 1][j] + sums[i][j - 1]
							- sums[i - 1][j - 1] + matrix[i][j];
			}
		}
	}
	
	private static int computeSum(int[][] matrix, int startRow, int endRow,
			int startCol, int endCol) {
		if (startRow == 0 && startCol == 0)
			return sums[endRow][endCol];
		else if (startRow == 0)
			return sums[endRow][endCol] - sums[endRow][startCol - 1];
		else if (startCol == 0)
			return sums[endRow][endCol] - sums[startRow - 1][endCol];
		else
			return sums[endRow][endCol] - sums[endRow][startCol - 1]
					- sums[startRow - 1][endCol]
					+ sums[startRow - 1][startCol - 1];
	}

	public static int[][] findSubmatrixWithMaxSum(int[][] matrix) {
		preComputeSums(matrix);
		int startRow = 0, endRow = 0;
		int startCol = 0, endCol = 0;
		int maxSum = Integer.MIN_VALUE;
		for (int i = 0; i < matrix.length; ++i) {
			for (int j = 0; j < matrix[i].length; ++j) {
				for (int rowPtr = i; rowPtr < matrix.length; ++rowPtr) {
					for (int colPtr = j; 
						colPtr < matrix[rowPtr].length; ++colPtr) {
						int sum = computeSum(matrix, i, rowPtr, j, colPtr);
						if (sum > maxSum) {
							maxSum = sum;
							startRow = i;
							endRow = rowPtr;
							startCol = j;
							endCol = colPtr;
						}
					}
				}
			}
		}

		int[][] subMatrix = new int[endRow - startRow + 1][endCol - startCol
				+ 1];
		for (int i = startRow; i <= endRow; ++i)
			System.arraycopy(matrix[i], startCol, subMatrix[i - startRow], 0,
					endCol - startCol + 1);
		return subMatrix;
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: