CareerCup

we can use kandane's to do so
getMaximumSubMatrixSum is function which needs to be called

public class MaximumSubMatrix {

	int kandane(int [] data) {
		int max =0;
		int sum =0;
		for(int i=0;i<data.length;i++) {
			sum+=data[i];
			sum = Math.max(0,sum);
			max=Math.max(max, sum);
		}
		return max;
	}
	public int getMaximumSubMatrixSum(int [][] data){
		int max =0;
		int COLS = data[0].length;
		int ROWS = data.length;
		for(int left = 0; left < COLS; left++) { // fix a left column
			int [] _data = new int[ROWS];
			for(int right = left; right < COLS; right++) { // fix a right column
				// now we will look all the data between left and right column
				for(int i=0;i<ROWS;i++)
					_data[i] += data[i][right];
				// find maximum sum in _data array using simple kandane's algo
				max = Math.max(max, kandane(_data));
			}
		}
		return max;	
	}

if M is of size nxn (does not have to be a square), this is a question solved in careercup book, brute force is O(n^6), optimized with O(n^4) additional space complexity O(n^2)
Additional space complexity is for precomputing calculating sum till (i,j)
sum[i][j] = sum[i - 1][j] +sum[i][j-1]-sum[i-1][j-1]+M[I,j]
and then selecting different matrices is O(n^4), the sum calculation is O(1)
sum[i2][j2] - sum[i2][j1 - 1] - sum[i1 - 1][j2] + sum[i1 - 1][j1 - 1];
just return max sum

this is an extension of max subarrary problem, can be done in O(n^3) for a n*n matrix

This can be easily solved with dynamic programming. Same logic as in max subarray problem.