Maximum Value Contiguous Subregion

Question

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.

Answer 1

First judge what kind of rectangle I want to get. If the negative numbers are the majority, the rectangle is very small. On the contrary, this rectangle is very large. Choose from the sum of the rectangle. The worst case is the negative number is not the majority but very small or otherwise. But divide into two situations will quicker in most case.

If it is a large rectangle, I will shrink from the outside to the inside, as long as the sum of the reduced circles is negative, continue to shrink. If it is positive, check the negative number in the circle and the size of the circle. If it is still regular, Otherwise continue until the confirmation is correct, going back to the best known result.

If it is a small rectangle, it expands from the largest positive number, and each positive number expands to the best result when the total is negative, until the traversal of all positive possibilities.