From: James Edward Gray II <james@...>
Date: 2007-07-16T23:02:16+09:00
Subject: Fwd: [QUIZ-Solution] Maximum Sub-Array (#131)

Begin forwarded message:

> From: "Eric Mahurin" <eric.mahurin@gmail.com>
> Date: July 16, 2007 8:13:56 AM CDT
> To: "James Edward Gray II" <james@grayproductions.net>
> Subject: Fwd: [QUIZ-Solution] Maximum Sub-Array (#131)
>
> James,
>
> I messed up on my first solution.  Could you put this on  
> rubyquiz.com instead?
>
> Thanks,
>
> Eric
>
> ---------- Forwarded message ----------
> From: Eric Mahurin <eric.mahurin@gmail.com>
> Date: Jul 15, 2007 9:20 PM
> Subject: Re: [QUIZ-Solution] Maximum Sub-Array (#131)
> To: ruby-talk ML <ruby-talk@ruby-lang.org>
>
>
> 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]