An interesting problem

[Mark Blackman]

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.

- Mark

> 
> Thanks in advance,
> 
> Paul
>