# An interesting problem

David Landgren david at landgren.net
Wed Jan 3 21:02:24 GMT 2007

```Mark Blackman did write:
> Paul Orrock wrote:
>> Hi,
>>
>> I have a problem for a project I'm working on and much googling,
>> cpanning and brain overheating has not yielded an answer. So I'm
>> turning to the great london perlmongers to see if anyone has any ideas.
>>
>> I have a 2d table of data with each cell having a positive or negative
>> value. By summing a range of data which is x columns by y rows
>> anywhere in the table it will come up with a positive or negative
>> figure. What I need to find is which range yields the highest positive
>> result. The range can be any size and have its first cell at any point
>> in the table.
>>
>> For example a table as follows, (apologies to those not using monospace)
>>
>>    A  B  C  D
>> W  2 -3 -1  3
>> X -1  5  3 -2
>> Y -7  2 -1 -1
>> Z  1  4  2  0
>>
>> The area I want starts at column BX and runs down and right to column
>> CZ with a total of 16.
>>
>> Does anyone have any clever ways of doing this other than brute
>> forcing it by checking every possible range (in a 100 by 30 table).
>> And if brute forcing it is the only option (which I suspect it is)
>> does anyone have any clever ways of doing it. Using numbers for
>> columns and rows instead of letters is fine.
>
> sounds like a very NP-hard problem to do deterministically, I'd guess
> 2d autocorrelation might get you part of the way though, i.e.
> determining local and global maxima.

It is in fact NP-hard. The only way to find the minimum or maximum
submatrix is to brute-force all the 1..n x 1..m sub-matrices. One can
obtain a reasonable answer in a reasonable amount of time if one is
willing to forgo the best answer :)

simulated annealing might be another thing to search for.

David
```