How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers,,, First, find a prefix-sum on each column (O(N^2)). This

How to find the Rectangle of Max sum in a 2D matrix consisting of both +ve and -ve numbers...

First, find a prefix-sum on each column (O(N^2)). This is done so that we can later on compute the sum of consecutive rows in O(1) complexity.
Now, observe all possible row-pairs (O(N^2)), and for each pair, you can see that we can get the sum of each "column" in O(1) complexity. This will provide us with a feeling that you can view the contiguous rows within each row-pair as only one row per column. Thus, we have a somewhat a one-dimensional array of column sums.
To find the maximum contiguous elements in one-dimensional array, there is a Kadane's algorithm which is O(N).
All the steps above gives O(N^3) algorithm.