James Gray
7/16/2007 2:02:00 PM
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]