 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->{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";
[download]```

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?