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.

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

Update: The error is my environment not tilly's code!

With -s command line switch disabled, his code produces the following output for the 'failing test':

c:\test>perl tilly.pl -1 -2 -3 -4 -5 -6 -7 -8 -9
Start: 0
End: -1
Sum: 0
Numbers:
[download]

which is not totally incorrect.

Your's needs to be a little more complex though.

c:\test>tilly -1 -2 -3 -4 -5 -6 -7 -8 -9
Start: 5
End: 11
Sum: 26
Numbers: 5 8 4 4 -3 5 3
[download]

As for the interesting case of all negative numbers noted by BrowserUK++, coming from the initial "best" intervall being an empty list with sum zero, which will then serve as an upper limit not to surpass in the loop.

I think that can be dealt with by

Update: hiding original approach in readmore tags, since it is incorrect and now obsolete

(start Update insert)

So instead of messing that much with tilly's code I now concentrate on the "best" initialization before we enter the loop.

For my addendum loops through the beginning of @array as long as we are still seeing negative numbers.

When we finally see a non-negative we proceed with tilly's code from there.

To be prepared for the case that all elements are negative, we adjust the *_start, *_end, best*, cur* variables heading for the max (= least negative number) instead.

Which leaves me with some code not so elegant anymore
Maybe someone else is able to reimplement tilly's original idea also to work for all negative numbers in a more elegant/compact/concise way

(end update insert)

Otherwise I think the idea behind the algorithm presented by tilly++ is correct, or so I hope.

Update: Still not correct as presented. Back to the drawing board...

Speaking mathematically, the sum of the empty set is a perfectly valid sum of consecutive integers, and its value is 0. But you can change the problem to exclude the empty sum as follows:

#! /usr/bin/perl -w
use strict;

my @array = @ARGV ? @ARGV : qw(3 2 8 9 -25 5 8 4 4 -3 5 3 -10);

my $cur = my $best_start = my $best_end = my $cur_start = 0;
my $best = $array[0];

for (0..$#array) {
  $cur += $array[$_];

  if ($best < $cur) {
    $best = $cur;
    $best_start = $cur_start;
    $best_end = $_;
  }

  if ($cur < 0) {
    $cur = 0;
    $cur_start = $_ + 1;
  }
}

print qq(Start: $best_start
End: $best_end
Sum: $best
Numbers: @array[$best_start..$best_end]
);
[download]

Ah, just a matter of finding the right abstraction / realization that allows you to see why each algorithm always finds the right answer. For this one, a simple two-part realization does it:

(----- the full list -------)
       [-- max sum --]
  <neg><pos><- plus ->
[download]

If a subrange has the maximum sum, then splitting that range into two new subranges will always give you two ranges that each have non-negative sums (otherwise the other new subrange would be an even better choice). In particular, if "<pos>" has a negative sum, then "[-- max sum --]" does not have the maximum sum.

Conversely, any non-empty subrange directly to the left ("<neg>") of the max-sum subrange will have a negative sum (else adding that in would give a better sum).

Another observation is that you can always add the consecutive postive or negative numbers together, so you only need to deal with the case when the sequence is alternating, +-+-+-+-...+. That may simplify the logic. But tilly's solution is certainly elegant, the only "drawback" is that it's not symmetric, would be more beautiful if it went from both ends.