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".

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.