The solution you described is O(@array ** 2) - it's complexity is proportional to the square of the number of items in the array. I think it can be done in O(@array) instead - but perhaps I have a mistake in my logic?
Sample code follows:
#!/usr/bin/perl -w
use strict;
# http://perlmonks.org/index.pl?node_id=570420
my @array;
if (@ARGV) {
@array = @ARGV;
} else {
@array = qw( 3 2 8 9 -25 5 8 4 4 -3 5 3 -10 );
}
my $start = -1;
my @groups;
my $cursign = 0;
foreach (@array) {
$start ++;
next unless $_;
if (($_ > 0 and $cursign == 1) or
($_ < 0 and $cursign == -1)) {
$groups[-1]->{sum} += $_;
$groups[-1]->{end} = $start;
} elsif ($cursign != 0) {
$cursign *= -1;
push @groups, {sum => $_, start => $start, end => $start};
} else {
$cursign = ($_ > 0 ? 1 : -1);
push @groups, {sum => $_, start => $start, end => $start};
}
}
# if the first or last set is negative, just drop it
if ($groups[-1]->{sum} < 0) {
pop @groups;
}
if ($groups[0]->{sum} < 0) {
shift @groups;
}
my ($cur_start, $cur_total);
my ($best_start, $best_total, $best_end) = (0, 0, 0);
while (my $group = shift @groups) {
$cur_start = $group->{start} unless defined $cur_start;
if ($group->{sum} + $cur_total < 0) {
if ($cur_total > $best_total) {
$best_total = $cur_total;
$best_start = $cur_start;
$best_end = $group->{start}-1;
}
$cur_total = 0;
$cur_start = undef;
next;
}
$cur_total += $group->{sum};
if ($cur_total > $best_total) {
$best_total = $cur_total;
$best_start = $cur_start;
$best_end = $group->{end};
}
print "$group->{sum}, $cur_total, $best_total\n";
}
$best_end = $#array unless defined $best_end;
print "$best_total $best_start - $best_end\n";
Basically, it's similar to what you added at the end - go over the array, adding up the items until you find one that just cancels them out. Then start over from that point.
Does anyone spot a mistake here?