An interesting problem
paulo at digitalcraftsmen.net
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 london.pm