Greetings monks!

A problem has come to my attention. Given an arbitrary sized array of integers in an arbitrary order, whats the sequence of consecutive integers that results in the largest sum.*

Given the array: 
array = {3 2 8 9 -25 5 8 4 4 -3 5 3 -10}
The subset with the largest sum would be: 
largestsubset = {5 8 4 4 -3 5 3}
This is what I came up with: 
#!/usr/bin/perl

use strict;
use warnings;

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

my $length = scalar(@array);
my $sidx;
my $eidx;
my $max = 0;

my $start = 0;
while($start < $length) {
        my $sum = $array[$start];
        for(my $end = ($start + 1); $end < $length; $end++) {
                $sum += $array[$end];
                if($sum > $max) {
                        $sidx = $start;
                        $eidx = $end;
                        $max = $sum;
                }
        }
        $start++;
}

[download]
Which gives you the nice and handy: 
Start: 5 End: 11

Now of course that isn't pretty, but it works nicely for smaller sets. Only problem I could see is if the sets grow to an unreasonable size. Are there any more elegant ways of going at this?

One of my ideas was watching the value of sum and if it reached a negative value then break out of the inner loop.




* Yes, this is a homework question if you've guessed, but I already have a viable solution, and am just interested in more efficient algorithms, and not to mention we have to use Java.

In reply to 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.