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: 
With the help of the [Algorithmist](http://www.algorithmist.com/index.php/UVa_108) and Larry and a modification of Kadane's Algorithm, here is my solution:

```
int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }
    int maxSoFar = 0;
    int min , subMatrix;
    //iterate over the possible combinations applying Kadane's Alg.
    for (int i = 0; i < dim; i++) {
        for (int j = i; j < dim; j++) {
            min = 0;
            subMatrix = 0;
            for (int k = 0; k < dim; k++) {
                if (i == 0) {
                    subMatrix += ps[j][k];
                } else {
                    subMatrix += ps[j][k] - ps[i - 1 ][k];
                }
                if(subMatrix < min){
                    min = subMatrix;
                }
                if((subMatrix - min) > maxSoFar){
                    maxSoFar = subMatrix - min;
                }                    
            }
        }
    }

```

The only thing left is to determine the submatrix elements, i.e: the top left and the bottom right corner of the submatrix. Anyone suggestion?
Have a look at [JAMA](http://math.nist.gov/javanumerics/jama/ "JAMA") package; I believe it will make your life easier.