On Sunday 15 July 2007 15:18, Eric Mahurin wrote:
> Here is a O(n) solution.  This simply finds the max accumulation minus
> the min accumulation.  I haven't done too much testing, so I don't
> know if it handles all of the corner cases.
> 
> <snip>

FYI, your solution does indeed fail in some cases:

irb(main):052:0> arr = [-2,0,0,4,-5,1]
=> [-2, 0, 0, 4, -5, 1]
irb(main):053:0> max_subarray arr
=> [-2, 0, 0, 4]


-- 
Jesse Merriman
jessemerriman / warpmail.net
http://www.jessemerriman.com/