# An interesting problem

Dan Rowles d.rowles at outcometechnologies.com
Thu Jan 4 18:23:04 GMT 2007

```Set the max to the value of the cell at 0,0 before starting the inner
loop. Then, you can remove the "defined" check.

Dan

McGlinchy, Alistair wrote:
> Simon Matthews wrote:
>> One thing that might speed it up even further would be to
>> pre-cache the
>> total of (0..x, 0..y) for each x and y.
>>
>> Then for a particular tile (l..r, t..b):
>>
>> 0   l   r
>> +---|---|----+
>> |...|///|    |
>> ----+---+----- t
>> |\\\|XXX|    |
>> |\\\|XXX|    |
>> ----+---+----- b
>> |   |   |    |
>> +---|---|----+
>>
>> Total of ... will be T(l,t)
>> Total of /// will be T(r,t) - T(l,r)
>> Total of \\\ will be T(l,b) - T(l,r)
>>
>> So the total of XXX will be:
>>    T(r,b) - ( total of /// + total of \\\ + total of ... )
>>  = T(r,b) - ( T(r,t) - T(l,r) + T(l,b) - T(l,r) + T(l,r) )
>>  = T(r,b) - T(r,t) + T(l,t) - T(l,b)
>>
>> Simon
>
> I've had a go at this method. Its slower than my previous post (up to
> 40secs from about 16secs).  There's some hash ref caching that may help
> speed it up a bit. What I cannot work out is how you think this method
>
> By the way does anyone have a better method doing the max calculation. I
> loathe  "if (!defined(\$max) or \$max  < \$val)" line.
>
> Cheers
>
> Alistair
>
>
> __CODE__
>
> # Same top bit as before.
>
> sub prepare_origin_range {
>     # Prepare a cache of range sums from he origin to \$x,\$y
>
>     # Initialise the top left row
>     \$sum_from_origin[0][0] = \$table[0][0];
>
>     # Complete the calulations for the rest of \$y where \$x==0.
>     for my \$y        (1 .. \$max_y) {
>         \$sum_from_origin[0][\$y] =
>             \$sum_from_origin[0][\$y-1] +
>             \$table[0][\$y];
>     }
>     # Populate the whole table of the \$x >0
>     for my \$x        (1 .. \$max_x) {
>         #@row_sum is the sume of the slice (0..\$y) of the \$x'th row
>         my @row_sum = (\$table[\$x][0]);
>         \$sum_from_origin[\$x][0] = \$row_sum[0];
>         for my \$y        (1 .. \$max_y) {
>             \$row_sum[\$y]= \$row_sum[\$y-1] + \$table[\$x][\$y];
>             \$sum_from_origin[\$x][\$y] = \$sum_from_origin[\$x-1][\$y] +
> \$row_sum[\$y];
>         }
>     }
> }
>
> sub max_sum_range {
>     my \$max;
>     for my \$x1(0   .. \$max_x) {
>     for my \$y1(0   .. \$max_y) {
>     for my \$x2(\$x1 .. \$max_x) {
>     for my \$y2(\$y1 .. \$max_y) {
>         #+---|---|
>         #| A | B |
>         #----+---+
>         #| C | D |
>         #----+---+
>         my \$A    = \$sum_from_origin[\$x1][\$y1];
>         my \$AB   = \$sum_from_origin[\$x1][\$y2];
>         my \$AC   = \$sum_from_origin[\$x2][\$y1];
>         my \$ABCD = \$sum_from_origin[\$x2][\$y2];
>         my \$val = \$ABCD - \$AB - \$AC + \$A;
>         if (!defined(\$max) or \$max  < \$val) {
>             \$max = \$val;
>             print "Range (\$x1,\$y1) , (\$x2,\$y2) is better with \$val\n";
>             @result = (\$x1,\$y1,\$x2,\$y2);
>         }
>     }}}}
>     return (\$max, @result);
> }
>
>
> **********************************************************************
> Registered Office:
> Marks and Spencer plc
> Waterside House
> London
> W2 1NW
>
> Registered No. 214436 in England and Wales.
>
> Telephone (020) 7935 4422
> Facsimile (020) 7487 2670
>
> <<www.marksandspencer.com>>
>
> Please note that electronic mail may be monitored.
>
> This e-mail is confidential. If you received it by mistake, please let us know and then delete it from your system; you should not copy, disclose, or distribute its contents to anyone nor act in reliance on this e-mail, as this is prohibited and may be unlawful.
> 2005
>
>
>

--
Dan Rowles
CTO
Outcome Technologies

_________________________________

t: +44 (0)207 656 2460
f: +44 (0)709 230 6588
m: +44 (0)798 076 8143
e: d.rowles at outcometechnologies.com
w: http://www.outcometechnologies.com
BUPA House
15-19 Bloomsbury Way
London WC1A 2BA
_________________________________

***This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they are