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:

  1. We did not set $cur_start to $x. Then when $_ was $x-1, $cur was greater than or equal to 0. Which means that there is some $z < $x such that sum(@array[$z..($x-1)]) >= 0. But then sum(@array[$z..$y]) >= sum(@array[$x..$y]) and @array[$x..$y] is not the longest best because there is a longer one that is at least as good.
  2. We did set $cur_start to $x. Then there is some $z with $x <= $z <= $y with sum(@array[$x..$z]) < 0. Now we have two more cases:
    1. $z = $y In this case sum(@array[$x..$y]) < 0 and we are beaten by the empty set.
    2. $z < $y In this case sum(@array[$x..$y]) < sum(@array[$z..$y]) and we are not best.
And there you have it. If we did not look at a set of consecutive integers, it is not best. Since we took the max of the rest, we must have found the best one.

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 reply to Re^2: Largest Sum of Consecutive Integers - explanation by tilly
in thread Largest Sum of Consecutive Integers by OverlordQ

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.