The maximal sum of a rectangular sub-array

Question

Given an array of real-valued numbers, A[1..n,1..n], I wish to find the sub-array

B = A[i..j,s..t]

with 1 <= i <= j <= n, and 1 <= s <= t <= n

such that the sum of the numbers in B is maximized. Is it possible to solve this using dynamic programming? I spoke to one of the OR professors at Aarhus University, and he didn't know how to do it, and said that he had difficulty seeing how it could have the optimal substructure quality.

But IS it possible? If yes, how? If not, why?

I already know of an algorithm that runs in O(n^3) time, by reducing it to n(n+1)/2 subproblems of complexity O(n), but that seems like it's a bit slow. I know that an optimal algorithm would run in Omega(n) time, but I'm hoping that dynamic programming could be used for making it run in O(n^2) time.

Original question summarized

I added this section because I felt some people has misinterpreted the point of my question. The original question was:

1. Is it possible to use dynamic programming to solve the above problem in O(n^2) time? If yes, how? If no, why not?

Additional questions:

I added a new questions here. More might be added later:

1. In order to use dynamic programming, I need to make use of solutions to easily solved subproblems (Or else the point is moot). The structure of the problem is such, that if we take a subarray B = A[1..m,1..m] of A[1..n,1..n] where m < n, then the optimal solution for array B is at most as good as in A, trivially, since the same solution is feasible in A. To use dynamic programming, it is therefore reasonable to ask: What is the relationship between the optimal subarray of A[1..i,1..i] and the optimal subarray of A[1..i+1,1..i+1]?

Answer 1

A possibly useful optimization would be to skip checking a,b pairs when you can calculate that it is impossible for the score to beat the current best.

For example, one way of doing this would be:

1. Run Kadane's algorithm on every row (n repeats of O(n) algorithm = O(n^2)) and store the maximum value in an array M.
2. Compute the vertical prefix sum of array M in O(n) time
3. Now for each a,b pair we can use our vertical prefix sum to get an upper bound for the sum that can be got from this pairing and skip the test if it is lower than our current best value.

This will probably work best if you also run Kadane's algorithm on the array M and test the resulting a,b pair first.

In the best case (e.g. the image contains a black background and a white rectangle somewhere inside) this will find the answer in O(n^2), but for more complicated inputs it will still take O(n^3).

WARNING: In practice, this trick will probably only help for a very small set of inputs, for the cost of slowing down the majority...

EDIT: Some additional explanation:

For row i, M[i] contains the largest value that can be got from any height 1 rectangle of the form A[i..i,x..y].

We define a new array P[i] (called the vertical prefix sum in the description above).

P[0]=0
P[i+1]=M[i]+P[i]

For a given choice of rows s and t we can get a quick estimate of the highest value that can be got from any rectangle of the form A[s..t,x..y] by computing sum(M[i] for i in range(s,t+1)). This actually gives us the value of a shape something like:

...           Row s
 ....
 .......
   ....       Row t

formed by taking the best height 1 rectangle from each row between s and t.

The array P[i] is useful because P[i] = sum(M[j] for j in range(i)), so we can compute sum(M[i] for i in range(s,t+1)) = P[t+1]-P[s] in O(1) time.