Find the Sub-Matrix with the Largest Sum in a Matrix

Problem: Given a m*n matrix that is made up of integers (positive and negative), find the sub-matrix with the largest sum.

Solution: There is an O(n) algorithm to find the sub-array with the largest sum in a one-dimension array. So here, we will try to reduce our problem to the one-dimension array problem.

1. Assume the sub-matrix is between row a and b where 0<=a<=b<=m,  then we discard all the rows that are out of the range [a, b]. We then squeeze the sub-matrix into a one-dimension array. How to squeeze? Just use the sum of the elements remaining in each row to replace that row! Therefore we get a one dimensional array with n elements (each element is a sum). 
2. Then apply the O(n) algorithm we mentioned previously, we will get the sub-array with the largest sum in this one-dimension array, which is actually the sub-matrix between row a and b with the largest sum.
3. Until now, we have examined one pair a and b. If we try all the combination of a and b, we will be able to find the the sub-matrix in the with the largest sum in the m*n matrix. Assume n<m, we need repeat n^2 such operation. Then the overall time complexity is O(n^3). Naive way may take O(n^4). 
4. In order to make the "squeeze" operation (summing the column elements) with a constant time complexity, we need to do some pre-processing. We just need to calculate the prefix-sum. For example, c[i][j] = a[0][j] + a[1][j] +...+ a[i][j] . It is easy to calculate this for the whole matrix with time complexity O(n^2).