Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

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

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; } } # Adjust accordingly if leading/trailing negatives 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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://570437]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (8)
As of 2018-06-17 23:01 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (107 votes). Check out past polls.