Don't ask to ask, just ask | |
PerlMonks |
Re^2: Largest Sum of Consecutive Integers - explanationby tilly (Archbishop) |
on Aug 31, 2006 at 18:34 UTC ( [id://570659]=note: print w/replies, xml ) | Need Help?? |
I was asked in chatter to explain why this works. Here is the explanation. The sets of consecutive integers are made up of the empty set, and ranges @array[$x..$y] with $x < $y. This algorithm examines a set of sums from sets of consecutive integes and selects the best of that collection. What we need to demonstrate is that we looked at one that was best. I'll actually show that none of the sets we skipped were the longest best one. (We may not choose the longest best one, but if we can show we looked at it, then we'll definitely got the best possible score.) Or, equivalently, that every set we skipped either has a lower sum or a shorter length than some other set. We look at the empty set, so all of the sets we skip look like @array[$x..$y]. We have to show that any we skip is not the longest best. Let us divide this into cases:
The proof for the slight variation of the algorithm that I presented excluding the empty set is similar but simpler. I leave it as an exercise to go through that proof and see why I had to make the code changes that I did. Update: I had a slight oversight the first time around. I fixed that by replacing "best" with "longest best".
In Section
Seekers of Perl Wisdom
|
|