Re: Largest Sum of Consecutive Integers

[zigdon]

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?