An interesting problem

Paul Orrock paulo at
Wed Jan 3 14:03:34 GMT 2007


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.

Thanks in advance,


More information about the mailing list