Beefy Boxes and Bandwidth Generously Provided by pair Networks
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; } } # 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?
Username:
Password:

What's my password?
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?