Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: Largest Sum of Consecutive Integers

by Limbic~Region (Chancellor)
on Aug 30, 2006 at 17:50 UTC ( [id://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
Domain Nodelet?
Node Status?
node history
Node Type: note [id://570437]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (6)
As of 2024-03-28 14:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found