Question: **Input**: A 2-dimensional array NxN - Matrix - with positive and negative elements.  

**Output**: A submatrix of any size such that its summation is the maximum among all possible submatrices.

**Requirement**: Algorithm complexity to be of **O(N^3)**  

**History:** With the help of the Algorithmist, Larry and a modification of Kadane's Algorithm, i managed to solve the problem **partly** which is determining the summation only - below in Java.  

Thanks to **Ernesto** who managed to solve the rest of the problem which is determining the boundaries of the matrix i.e. top-left, bottom-right corners - below in Ruby.

Answer: 
Have a look at [JAMA](http://math.nist.gov/javanumerics/jama/ "JAMA") package; I believe it will make your life easier.
Here is my solution. It's O(n^3) in time and O(n^2) space.
<https://gist.github.com/toliuweijing/6097144>

```
// 0th O(n) on all candidate bottoms @B.
// 1th O(n) on candidate tops @T.
// 2th O(n) on finding the maximum @left/@right match.
int maxRect(vector<vector<int> >& mat) {
    int n               = mat.size();
    vector<vector<int> >& colSum = mat;

    for (int i = 1 ; i < n ; ++i) 
    for (int j = 0 ; j < n ; ++j)
        colSum[i][j] += colSum[i-1][j];

    int optrect = 0;
    for (int b = 0 ; b < n ; ++b) {
        for (int t = 0 ; t <= b ; ++t) {
            int minLeft = 0;
            int rowSum[n];
            for (int i = 0 ; i < n ; ++i) {
                int col = t == 0 ? colSum[b][i] : colSum[b][i] - colSum[t-1][i];
                rowSum[i] = i == 0? col : col + rowSum[i-1];
                optrect = max(optrect, rowSum[i] - minLeft); 
                minLeft = min(minLeft, rowSum[i]);
            }
        }
    }

    return optrect;
}

```