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]