An interesting problem

[Andy Armstrong]

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