# An interesting problem

Simon Matthews spm at flirble.org
Fri Jan 5 20:45:15 GMT 2007

```* McGlinchy, Alistair (Alistair.McGlinchy at marks-and-spencer.com) [070104 17:41]:
> 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.
>
> 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
>

I've done some experiments and replacing the use of the intermediate
changed the run time from 25 seconds to around 15 seconds (the previous
source code takes 17 seconds to run). I reduced this even further down to
~10 seconds by changing the function to cache some of the intermediate
values.

I noticed a problem where it was giving the wrong results - when
calculating \$A etc it needs to refer to the cell(s) before the range area.
Hence:
\$A = \$sum_from_origin[\$x1-1][\$y1-1];
\$AB = \$sum_from_origin[\$x1-1][\$y2];
\$AC = \$sum_from_origin[\$x2][\$y1-1];

This then needs handling for the cases where \$x1 and \$y1 are 0, so I ended up
inserting 0s into the \$sum_from_origin area to cope with this.

See below for the code with the appropriate modifications.

Simon

__CODE__

# Top part as before

sub prepare_origin_range {

# Increment since sum_from_original has an extra row and column for
# 0s
\$max_x++;
\$max_y++;

# \$sum_from_origin[\$x][\$y] is the sum of the cells from
# 0 .. \$x and 0 .. \$y in row
for my \$y (0 .. \$max_y) {
\$sum_from_origin[0][\$y] = 0;
}

for my \$x (1 .. \$max_x) {
my \$tot = 0;
\$sum_from_origin[\$x][0] = 0;

for my \$y (1 .. \$max_y) {
\$tot += \$table[\$x-1][\$y-1];
\$sum_from_origin[\$x][\$y] = \$sum_from_origin[\$x-1][\$y] + \$tot;
}
}
}

sub max_sum_range {
my \$max = \$sum_from_origin[1][1];
my \$val;

for my \$x1(1   .. \$max_x) {
for my \$y1(1   .. \$max_y) {
my \$A    = \$sum_from_origin[\$x1-1][\$y1-1];

for my \$x2(\$x1 .. \$max_x) {
my \$tmp   = \$A - \$sum_from_origin[\$x2][\$y1-1];

for my \$y2(\$y1 .. \$max_y) {
#+---|---|
#| A | B |
#----+---+
#| C | D |
#----+---+
\$val = \$sum_from_origin[\$x2][\$y2] -   # ABCD
\$sum_from_origin[\$x1-1][\$y2] +    # AC
\$tmp                              # (A - AB)
#			\$sum_from_origin[\$x1-1][\$y1-1] -  # A
#			\$sum_from_origin[\$x2][\$y1-1]      # AB
;

if (\$max  < \$val) {
\$max = \$val;
print "Range (\$x1,\$y1) , (\$x2,\$y2) is better with \$val\n";
@result = (\$x1,\$y1,\$x2,\$y2);
}
}
}
}
}

# Fix up the coordinates returned to be 0-based
\$result[0]--;
\$result[1]--;
\$result[2]--;
\$result[3]--;

return (\$max, @result);
}

__EDOC__

```