On Jul 15, 2007, at 20:19 , Jesse Merriman wrote:

> Not to be the downer who points out everyone's problems, but here's  
> a bug:

No problem at all! Thanks for taking a look at my work :)

> irb(main):008:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9,  
> -19, -36, -6,
>                       -20, -4, -23, -25, 48, -22, 22, 5, -21, -33,  
> 37, 39,
>                       -22, 11, -44, -40, -37, -26]
> irb(main):009:0> arr.max_sub_array
> => [37, 39, 10]

This should be a bit more pleasing :)

irb(main):002:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19,  
-36, -6,
                            -20, -4, -23, -25, 48, -22, 22, 5, -21,  
-33, 37, 39,
                            -22, 11, -44, -40, -37, -26]
irb(main):005:0> arr.max_sub_array
=> [46, -8, 43]

Updated code follows below signature:

Michael Glaesemann
grzm seespotcode net

class Array
   def max_sub_array
     return [] if self.empty?
     self.max_sub_arrayr[0]
   end

   def max_sub_arrayr
     ary = self.clone
     sub_ary = Array.new.push(ary.shift)
     sum = sub_ary[0]
     max_sub_ary = sub_ary.dup
     max_sum = sum
     done = false
     ary.each_with_index do |n,i|
       if sum > 0
         if sum + n > 0
           sum += n
           sub_ary.push(n)
         else
           sub_ary, sum = ary.dup.slice(i..(ary.size-1)).max_sub_arrayr
           done = true
         end
       elsif sum <= n
         sub_ary, sum = ary.dup.slice(i..(ary.size-1)).max_sub_arrayr
         done = true
       end
       if sum > max_sum
         max_sum = sum
         max_sub_ary = sub_ary.dup
       end
       break if done
     end
     return max_sub_ary, max_sum
   end
end