Finding the heavier rectangle

[Shahab]

Hi, everybody.

Having a matrix of numbers (n*n), we want to find the (x1,y1) and (x2,y2) 1<=x1<=x2<=n , 1<=y1<=y2<=n such that the sum of the numbers in this rectangle is bigger than any other rectangle in this matrix.

I have a solution with O(n^3) but I think that we must have a better solution ( for example with O(n^2)). If you have one , plz tell me that , and if you think we haven't such a solution , tell me why?


Sincerely yours.
Shahab Tasharrofi

[Yarin]

This is problem 108 as I'm sure you know, and I'm pretty certain it is a well established fact that you can't, in the general case, solve this faster than N^3. I'm afraid I have no idea how to prove this, but it seems like a standard problem so I think I should have heard if there's a N^2 solution.

[arnsfelt]

Actually there is a faster algorithm than O(n^3).
There was one in a siam journal some years ago.
It will probably not be faster on input sizes considered here, though.

[Yarin]

Umm, complexity doesn't matter on input size. In any case, do you have any reference to that algorithm?

[Shahab]

Hi, everybody

Now let's talk about a restircted form of this algorithm. Having a matrix of 0 and 1, we must find the biggest rectangle that includes only the 0's (like the problem 10074). surely, we can find the solution with changing the 1's to -(n^2+1) and 0's to 1 where n represents the size of the matrix. but what's the best solution(also I have no idea better than O(n^3)) ? I will be glad to hear your opinions.

Sincerely yours,
Shahab Tasharrofi

[arnsfelt]

Yarin: What do you mean by "complexity doesn't matter on input size" ?
Anyway, the reference:
Hisao Tamaki and Takeshi Tokuyama.
Algorithms for the maxium subarray problem based on matrix multiplication.
In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 446-452, San Francisco, California, 25-27 January 1998

Shahab: No, I will not explain the algorithm to you. Don't have the time, and besides if you have more than just a casual interest in it, you ought to read the paper yourself.

cheers

[rfcotta]

Well, this one Pedro Demasi teach me. Maybe I am forgetting something on the way, but that's the main idea..

Consider the linear case. You can find the greatest value on a submatrix in the following way:

1. The best you can get on the first position, is its own value
2. Go right. If what you had before can make the value greater, than the best on this position is its value + what you had before. Try to understand the sample below, where I have a matrix and following the best on each position

Code: Select all

Matrix ->   9  -1 -23   4   3   0  -1   0   2
Best   ->   9   8 -15   4   7   7   6   6   8


(the "Best" can be explained as:
  9 = 9
  8 = 9 - 1
  -15 = 8 - 23
  4 = 4 (if I included the -15 it was gonna be smaller)
  7 = 4 + 3
  7 = 0 + 7
  6 = -1 + 7
  6 = 0 + 6
  8 = 6 + 2
)

You can see that the greatest value of a submatrix is 9. Try with other values. This works.

Now we can have something similar to solve the 2-dimensional case. You have to do the followin:

0. i = 1. max = 0. v[1..n] = 0
1. Calculate the best value on each position for the line i
2. Sum these values to the values on the array v[] (v[0] += best[0]; v[1] += best[1]... v[n] += best[n])
3. If there's something grater than max on v[], make max = v[good_one]
4. i++
5. goto 1

We now got the best matrix starting from line 1 (the first line). We've got to try some other matrixes starting from lines 2, 3, ... n. So, repeat the proccess with i = 2, i = 3... i = n.

If someone can't understand something send an email to rafaelcotta@yahoo.com.br, that I'll post more details in here (I don't read the forums very frequently).

[Shahab]

Hi rfcotta,

I think that your algorithm won't provide the rectangular shape of the answer, it just provides the connectivity of it ( but also it won't be the answer even for the connected numbers , I think ). for example , check your algorithm with the following matrix.

-11 -11 -11 1
-11 -11 1 1
-11 1 1 1
1 1 1 1

I will be happy to know if i'm right about it.

Shahab Tasharrofi

[ingenious]

Can anyone please post a non-pseudo code with a solution
An O(n^3) solution works too.

I'm in big need, 10x in advance and Happy New Year 2004

[shamim]

Yarin: What do you mean by "complexity doesn't matter on input size" ?

Actually complexity is a function that determines the efficiency of a program. For different input size, same program will run in different time, but they are comparable by a constant factor.

For algorithms with different complexity, they can not be compared in the same manner.

[junbin]

If I understand it right, given a n by n matrix and the number m where m <= n, you want to find a m by m matrix within the n by n matrix such that the sum of the individual values within the m by m matrix is maximised.

There is no easy way to solve this question.. you have to use brute force searching. However, there is a way to reduce the time required by the brute force searching.

Using dynamic programming, you can easily reduce the number of operations required to a very minimum, then by simply tweaking your parameters for the dp table, you can dramatically increase the speed of the code.