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.
I would just parse the NxN array removing the -ves whatever remains is the highest sum of a sub matrix.

The question doesn't say you have to leave the original matrix intact or that the order matters.