5

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]?
Undreren
  • 2,811
  • 1
  • 22
  • 34
  • yes, there is a O(N^2) solution. I will try to explain it when I have time for that if no one does so before me(I am afraid I will not be able to do that in the next 24 hrs) – Ivaylo Strandjev Mar 20 '12 at 15:42
  • Does this algorithm have a name? – Undreren Mar 20 '12 at 15:44
  • 4
    Ooohhh, how exciting. Will @izomorphius die within the next 24 hours and leave us on tenterhooks for a couple of centuries like poor old Fermat ! I do hope not, but I fear (s)he is tempting fate. I will return tomorrow for a look. – High Performance Mark Mar 20 '12 at 15:47
  • 2
    See http://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum – Benjamin Mar 20 '12 at 15:49
  • @Benjamin : This is referring to an algorithm that runs in `O(n^3)` time. I wish to push it down to `O(n^2)` time. – Undreren Mar 20 '12 at 15:51
  • @HighPerformanceMark : I have a feeling that you do not agree that an `O(n^2)` time algorithm exists? – Undreren Mar 20 '12 at 15:52
  • 3
    @HighPerformanceMark I certainly hope not to die in the next 24 hours, but if that happens I will return and haunt the SO website until a smart guy writes the solution and gives eternal rest to my tortured soul. – Ivaylo Strandjev Mar 20 '12 at 15:56
  • 3
    @Undreren: I have no such feelings, I'm just worried about izomorphius. – High Performance Mark Mar 20 '12 at 15:57
  • @Undreren I don't think there is a name of the algorithm. However you can try to solve the linear case in linear time and the 2d solution is based on the same approach. – Ivaylo Strandjev Mar 20 '12 at 15:58
  • @izomorphius : Yes, that is how the `O(n^3)` approach came forth. I took all possible coherrent subsets of the array with height n, summed those vectors and used the `O(n)` algorithm for the 1xn case. It runs in `O(n^3)` time. – Undreren Mar 20 '12 at 16:02
  • Ohh... darn. That's my bad. This solution(which if I understand correctly what you mean) is the one I meant and indeed it has complexity O(N^3). I have done a mistake in calculating the complexity. No fate challenges and no surprising discoveries as a side note in someone's notebook. Sorry – Ivaylo Strandjev Mar 20 '12 at 16:25
  • 2
    @izomorphius : On the bright side, an untimely death for you on your way home will now be less of a nuissance for the rest of us ;) – Undreren Mar 20 '12 at 16:38

2 Answers2

3

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.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
1

From The Algorithmist, if you have an n by n array, the best you can do is O(n^3):

  • First, calculate the vertical prefix sum for all columns (an O(n^2) algorithm).
  • Second, assume that the maximum sub-array will be between row a and row b, inclusive. There are only O(n^2) a, b pairs such that a < b. Try each of them.
  • Since we already have the vertical prefix sum for all columns, the sum of elements in arr[a..b][c] for column c can be computed in O(1) time. This allows us to imagine each column sum as if it is a single element of a one-dimensional array across all columns (one dimensional array with one row and n columns).
  • There's an O(n) algorithm to compute the maximum sub-array for a one-dimensional array, known as Kadane's Algorithm.
  • Applying the Kadane's algorithm inside each a and b combination gives the total complexity of O(n3).

Given that you have an n by 2 array, you can get it down to O(n^2). The key, as above, is to use Kadane's algorithm

PengOne
  • 48,188
  • 17
  • 130
  • 149
  • 1
    Is there in fact a proof that `O(n^3)` is a tight upper bound? – Undreren Mar 20 '12 at 18:16
  • Besides, this post is really not helpful, since it just summarizes the `O(n^3)` algorithm I already knew. The last section is trivial. If you fix one dimension, then the amount of 1D arrays to use Kadane's algorithm on is trivially constant. – Undreren Mar 21 '12 at 07:57