On 7/15/07, Jesse Merriman <jesse.d.merriman / gmail.com> wrote:
> 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]

Thanks for pointing out my mistake.  I didn't handle the case when the
min accumulation comes after the max accumulation very well.  Now it
records the min index when it finds the best sub-array sum so far
(instead of blindly subtracting min from max at the end).  Here is a
corrected version w/ some testing in irb:

def max_subarray(seq)
    min_sum = 0
    min_i = -1
    max_delta = 0
    max_i = -1
    max_i0 = -1
    sum = 0
    seq.each_with_index { |val,i|
        sum += val
        delta = sum-min_sum
        if delta>max_delta
            max_delta = delta
            max_i = i
            max_i0 = min_i
        end
        if sum<min_sum
            min_sum = sum
            min_i = i
        end
    }
    seq[(max_i0+1)...(max_i+1)]
end



irb(main):001:0> require 'quiz131'
=> true
irb(main):002:0> max_subarray([-1, 2, 5, -1, 3, -2, 1])
=> [2, 5, -1, 3]
irb(main):003:0> max_subarray([-2,0,0,4,-5,1])
=> [0, 0, 4]
irb(main):004:0> max_subarray([-1, 2, 5, -1, 3, -2, 1])
=> [2, 5, -1, 3]
irb(main):005:0> max_subarray([31, -41, 59, 26, -53, 58, 97, -93, -23, 84] )
=> [59, 26, -53, 58, 97]
irb(main):006:0> max_subarray([])
=> []
irb(main):007:0> max_subarray([-10] )
=> []
irb(main):008:0> max_subarray([10])
=> [10]
irb(main):009:0> max_subarray([-5, 5])
=> [5]
irb(main):010:0> max_subarray([5, -5])
=> [5]