No such thing as a small change PerlMonks

### Re: Largest Sum of Consecutive Integers

by Limbic~Region (Chancellor)
 on Aug 30, 2006 at 17:50 UTC ( #570437=note: print w/replies, xml ) Need Help??

in reply to Largest Sum of Consecutive Integers

OverlordQ,
When you discussed this in the CB earlier, I was too busy thinking of my own solution to listen to what tye and ambrus had to say. I believe they felt an O(N) solution was possible. I believe this is an improvement on your code but doubt it is as efficient as what they had in mind.
```#!/usr/bin/perl
use strict;
use warnings;
use List::Util 'sum';

my @set = (3, 2, 8, 9, -25, 5, 8, 4, 4, -3, 5, 3, -10);
pop   @set while \$set[-1] < 0;
shift @set while \$set[0]  < 0;

my @neg = map {\$set[\$_] < 0 ? \$_ : () } 0 .. \$#set;
my @beg = (0, map {\$_ + 1} @neg);
my @end = (\$#set, map {\$_ - 1} @neg);
my (\$beg, \$end, \$max, \$sum) = (0) x 4;

for my \$i (@beg) {
for my \$j (@end) {
next if \$j < \$i;
\$sum = sum(@set[\$i .. \$j]);
(\$beg, \$end, \$max) = (\$i, \$j, \$sum) if \$sum > \$max;
}
}
print "\$beg .. \$end = \$max\n";
Since this is a homework assignment, I have not provided comments, but I will do so in the future for others that may come across this thread. Improvements are possible but hopefully different algorithms will be presented by others.

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://570437]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (4)
As of 2018-02-24 04:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When it is dark outside I am happiest to see ...

Results (310 votes). Check out past polls.

Notices?