Given an n x n matrix of integers, find four entries of the form
A[I1,J1], A[I2,J1], A[I1,J2], A[I2,J2] for i,j between 1 and n whose
sum is maximum. That is, find four corners of any sized rectangle in
the matrix with maximum sum. The algorithm must be strictly faster
than O(n^4) (brute force). I would appreciate a solution or technique
that could be extended to similar problems.

---

Clarification of Question by kingdave-ga on 08 Mar 2005 11:44 PST

There are probably a couple of things I need to clarify. I don't
particularly understand how your algorithm solves the problem
quadraticresidue, but let me clear a few things up for whoever is
reading this.

1) The matrix will be of size n x n, n >= 2 (I didn't mention that
before, but it follows from the requirement of four entries).
2) There is no requirement for any of the integers in the matrix to be
positive, so the maximum sum could be the smallest negative number.
3) I agree; the brute force method may take more than O(n^4), not
because the summing takes a long time (it's always the sum of four
entries, which I think would take a constant time, ie. it's always 4
no matter what n is), but because there are n^2 entries we have to
loop over, not just n.
4) I don't see how consecutive sums solve the problem. For example,
the matrix could be:

-1  -20  -10  -3
-4  -3   -16  -1
-5  -2   -3   -2
7   -5   -6   1

In which case the maximum sum would be the four corners (with sum 4).
So I guess I don't understand how consecutive summing can find this
answer, especially if you are skipping rows with no positives. Perhaps
I don't understand your solution correctly.

I appreciate your effort and hope that these clarifications help you
or someone else come up with the correct algorithm. If your algorithm
works correctly (perhaps after some change to include negatives),
maybe some pseudocode would help clarify for me. Thanks!

I don't know if this overall algorithm is the most optimal but it does
beat O(n^4) (which by the way, is not how long the simple brute force
algorithm would take - that's something more like O(n^6), because
summing the entries inside a trial rectangle takes about time O(n^2)).

Consider first an algorithm which can find the maximum consecutive sum
of a row, assuming the row contains a positive number.  This can be
done in linear time in a single sweep.  Such a sum will always begin
with a positive number.  We continue adding numbers (remembering the
largest sum) until the sum turns negative.  At this point we reset and
look for the next positive number.  We don't need to try anything
within the last region because any positive number in it must have
been followed by sufficient negativity to cancel it out.

The simple way of generalizing this will take O(n^4) time.  But we can
do it in O(n^3) time.  Select a row to start at; there are n such
rows.  You can simply run the above algorithm on this row and find the
maximum consecutive sum.  But then, you can consider both this row and
the next by taking the pairwise sum, keeping track of the running row
total in a separate array of n entries and running the maximum
consecutive sum algorithm on this array.  You can keep adding the next
array to your total, and each additional row to consider takes only
O(n) time because we spend O(n) time adding the extra row to the
running row total.  With n different rows to start at, this adds up to
time
sum(i*n,i=1..n)) = (n^3 + n^2)/2 = O(n^3).

If you would like me to implement this for you, let me know.

I see.  My algorithm sums the interior of the rectangle.  You just
want the corners.  I'll need to think about this some more.

OK, my new solution is somewhat similar in style and form but is
actually a lot simpler.  It too takes O(n^3) time.

Consider first an algorithm which can find the maximum pair of a row. 
This can be done in linear time with a single sweep.  We just remember
the best two things we've seen and update this every time we see
something better.

Now just try picking all pairs of rows.  When we pick a pair of rows,
we can sum those rows, pairwise, and find the maximum pair in that new
summed row.  (In fact, we don't need the extra O(n) space because we
can perform this sum dynamically as we do the single sweep for this
pair.)  There are O(n^2) such pairs and we do O(n) work on a pair, so
that's O(n^3) work.  Keep track of the best sum seen so far.

Again, I can code this up if necessary.

This is not necessarily the cleanest implementation and I haven't
tested it exhaustively, but hopefully it should give you an idea.

    public static int maxArraysSum(int[] x, int[] y, int[] ret) {
	if (x[0]+y[0] > x[1]+y[1]) {
	    ret[0] = 0;
	    ret[1] = 1;
	} else {
	    ret[0] = 1;
	    ret[1] = 0;
	}
	for (int i = 2; i < x.length; i++) {
	    if (x[i]+y[i] > x[ret[0]]+y[ret[0]]) {
		ret[1] = ret[0];
		ret[0] = i;
	    } else if (x[i]+y[i] > x[ret[1]]+y[ret[1]]) {
		ret[1] = i;
	    }
	}
	return x[ret[0]] + y[ret[0]] + x[ret[1]] + y[ret[1]];
	    
	
    }

    public static int getFourCorners(int[][] array, int[][] ret) {
	int[] bestRows = new int[]{0,1};
	int[] bestCols = new int[2];
	int bestVal = maxArraysSum(array[0], array[1], bestCols);
	int[] tmpCols = new int[2];
	for (int i = 0; i < array.length-1; i++) {
	    for (int j = i+1; j < array.length; j++) {
		int max = maxArraysSum(array[i], array[j], tmpCols);
		if (max > bestVal) {
		    bestVal = max;
		    bestRows[0] = i;
		    bestRows[1] = j;
		    bestCols[0] = tmpCols[0];
		    bestCols[1] = tmpCols[1];
		}
	    }
	}
	ret[0] = bestRows;
	ret[1] = bestCols;
	return bestVal;
    }

Yes, this is excellent. Your algorithm seems to be correct, and is
O(n^3). I really appreciate all your effort on this question.