CareerCup

Take an array of arr mxn. Now we can fill the arr[i][j] such that it contains the sum of all the elements with row<=i and col<=j in o(n^2).
Find max value in o(n^2) using:

Sum of all numbers in the square with left top corner at i,j will be as follows:

Also initialise the base condition (rows and columns to zero).
for(i=1;i<=m;i++){
	for(j=1;j<=n;j++){
		a[i][j] = input[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
	}
}

int max = 0;
for(i=1;i+k<=m;i++){
	for(j=1;j+k<=n;j++){
		int temp = a[i+k-1][j+k-1] - a[i-1][j+k-1] - a[i+k-1][j-1] + a[i-1][j-1];
		if(temp > max ){
			max = temp;
			row = i;
			col = j;
		}
		
	}
}

I will assume that value of each element is a positive integer.
Now if m < n the max value k can have is m. So lets
1)take a square of [m x m] i.e. ij,iq,pj, pq where i=j=0 and p=q=m, calculate the sum, compare with current max and store it if pass.
2) move the square forward by one column i.e. do j++ and q++, calculate the the sum, compare it with max and store points if pass.
repeat step 2 till q == n.
thus the biggest square with max sum is found. As an extension of this problem you could verify if the size of this square can be minimized.

Take an array of arr mxn. Now we can fill the arr[i][j] such that it contains the sum of all the elements with row<=i and col<=j in o(n^2).
Find max value in o(n^2) using:

Sum of all numbers in the square with left top corner at i,j will be as follows:

Also initialise the base condition (rows and columns to zero).
for(i=1;i<=m;i++){
	for(j=1;j<=n;j++){
		a[i][j] = input[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
	}
}

int max = 0;
for(i=1;i+k<=m;i++){
	for(j=1;j+k<=n;j++){
		int temp = a[i+k-1][j+k-1] - a[i-1][j+k-1] - a[i+k-1][j-1] + a[i-1][j-1];
		if(temp > max ){
			max = temp;
			row = i;
			col = j;
		}
		
	}
}

@Brij, your assumption is wrong. If all numbers are positive integers, and k <= m & n, then value of k = m & n for maximizing sum. The problem is interesting only if the matrix (m X n) contains negative numbers.

The problem is a typical Dynamic Prog. problem wherein we need to maximize the sum for any k <= m, n.

given an image, you want to find a square of size k that gives maximum size.
Convolve with a square filter of size k all 1's.