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: 
Here is a Java version of Ernesto implementation with some modifications:

```java
public int[][] findMaximumSubMatrix(int[][] matrix){
    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 maxSum = matrix[0][0];
    int top = 0, left = 0, bottom = 0, right = 0; 

    //Auxiliary variables 
    int[] sum = new int[dim];
    int[] pos = new int[dim];
    int localMax;                        

    for (int i = 0; i < dim; i++) {
        for (int k = i; k < dim; k++) {
            // Kadane over all columns with the i..k rows
            reset(sum);
            reset(pos);
            localMax = 0;
            //we keep track of the position of the max value over each Kadane's execution
            // notice that we do not keep track of the max value, but only its position
            sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
            for (int j = 1; j < dim; j++) {                    
                if (sum[j-1] > 0){
                    sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = pos[j-1];
                }else{
                    sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = j;
                }
                if (sum[j] > sum[localMax]){
                    localMax = j;
                }
            }//Kadane ends here

            if (sum[localMax] > maxSum){
                  /* sum[localMax] is the new max value
                    the corresponding submatrix goes from rows i..k.
                     and from columns pos[localMax]..localMax
                     */
                maxSum = sum[localMax];
                top = i;
                left = pos[localMax];
                bottom = k;
                right = localMax;
            }      
        }
    }
    System.out.println("Max SubMatrix determinant = " + maxSum);
    //composing the required matrix
    int[][] output = new int[bottom - top + 1][right - left + 1];
    for(int i = top, k = 0; i <= bottom; i++, k++){
        for(int j = left, l = 0; j <= right ; j++, l++){                
            output[k][l] = matrix[i][j];
        }
    }
    return output;
}

private void reset(int[] a) {
    for (int index = 0; index < a.length; index++) {
        a[index] = 0;
    }
}

```
this is my implementation of 2D Kadane algorithm. I think it is more clear. The concept is based on just kadane algorithm. The first and second loop of the main part (that is in the bottom of the code) is to pick every combination of the rows and 3rd loop is to use 1D kadane algorithm by every following column sum (that can be computed in const time because of preprocessing of matrix by subtracting values from two picked (from combintation) rows). Here is the code:

```
    int [][] m = {
            {1,-5,-5},
            {1,3,-5},
            {1,3,-5}
    };
    int N = m.length;

    // summing columns to be able to count sum between two rows in some column in const time
    for (int i=0; i<N; ++i)
        m[0][i] = m[0][i];
    for (int j=1; j<N; ++j)
        for (int i=0; i<N; ++i)
            m[j][i] = m[j][i] + m[j-1][i];

    int total_max = 0, sum;
    for (int i=0; i<N; ++i) {
        for (int k=i; k<N; ++k) { //for each combination of rows
            sum = 0;
            for (int j=0; j<N; j++) {       //kadane algorithm for every column
                sum += i==0 ? m[k][j] : m[k][j] - m[i-1][j]; //for first upper row is exception
                total_max = Math.max(sum, total_max);
            }
        }
    }

    System.out.println(total_max);

```