|Perl Monk, Perl Meditation|
Re: Largest Sum of Consecutive Integersby blokhead (Monsignor)
|on Aug 30, 2006 at 18:53 UTC||Need Help??|
Here's a linear-time algorithm that uses a much different approach than what tye has outlined.. It's probably needlessly dense, but I'm sorry, it came out of my brain in such a form.
If you want to find the best interval within array[i..j], then there are 3 possibilities.
We can compute total(i,j) without much overhead by keeping track of an accumulation array (sums of the form array[0..j]). This takes O(n) precomputation for the accumulation sums, and we can compute total(i,j) = sum(array[0..j]) - sum(array[0..i-1]) in constant time.
To compute each lbest(i,j), we split the interval into two intervals of half the size and recurse (with constant computation at this level). So to precompute all the lbest() and rbest() values that we need takes linear time total. Then with all of the lbest() and rbest() precomputed, to compute best(i,j) also just takes two recursive calls for intervals half the size. So the whole algorithm is linear.
OK, so this is probably a lot more machinery than tye suggests, but it gets the job done. I was formulating this before I saw his reply anyway. I wrote some example code for this, but I doubt anyone cares..
There's also the usual pain associated with modifying an algorithm that computes score of the best interval (which this does) to make it return the actual interval itself. ;)