Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: Largest Sum of Consecutive Integers

by zigdon (Deacon)
on Aug 30, 2006 at 17:54 UTC ( #570442=note: print w/replies, xml ) Need Help??


in reply to Largest Sum of Consecutive Integers

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?

-- zigdon

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://570442]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2019-05-25 23:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you enjoy 3D movies?



    Results (152 votes). Check out past polls.

    Notices?
    • (Sep 10, 2018 at 22:53 UTC) Welcome new users!