You are given a two dimentional array *A[1:n, 1..n]* of real numbers (possibly containing both positive and negative real numbers)*. *You want to find a rectangular sub-region of the array that maximizes the sum of that region. For example, the subarray S(1,2,5,8) consists of contiguous rectangle between A[1,2] to A[5,8], both corners inclusive, therefore, it has 35 total numbers.

Give the most efficient algorithm for this problem that you can.