# An interesting problem

Andy Armstrong andy at hexten.net
Wed Jan 3 21:08:23 GMT 2007

```On 3 Jan 2007, at 20:44, McGlinchy, Alistair wrote:
> my \$best;
> my @result;
> for (my \$x1 = 0   ; \$x1< \$max_x ; \$x1++) {
> for (my \$y1 = 0   ; \$y1< \$max_y ; \$y1++) {
> print "New \$x1,\$y1 for top left considerd\n";
> for (my \$x2 = \$x1 ; \$x2< \$max_x ; \$x2++) {
> for (my \$y2 = \$y1 ; \$y2< \$max_y ; \$y2++) {
>     my \$val = sum_range(\$x1, \$y1, \$x2, \$y2);
> #    print "Range (\$x1,\$y1) , (\$x2,\$y2) has val \$val\n";
>     if (!defined(\$best) or \$val > \$best) {
>         print "Range (\$x1,\$y1) , (\$x2,\$y2) is better with \$val\n";
>         \$best = \$val;
>         @result = (\$x1,\$y1,\$x2,\$y2);
>
>     }
> }}}}

You don't actually need to compute the sum from scratch every time -
you can instead adjust the sum every time one of the indexes changes
to include / exclude the part of the row / column that corresponds
with the change of index. For any non-trivial array though the
performance problem's going to come from having four nested loops.

How much data will you be working with in practice?

--
Andy Armstrong, hexten.net

```