From: Michael Glaesemann <grzm@...>
Date: 2007-07-16T06:17:56+09:00
Subject: [Solution][QUIZ] Maximum Sub-Array (#131)

Here's a solution which iterates over the array just once. Looks like  
I came up with a variant of the algorithm presented by Henrik Schmidt- 
M�ller, though I'm storing the local max sub array rather than just  
its delimiting indices. I'm not happy with the calls to slice  
(especially as they require calculating the size of the array), but  
I'm pleased that I came up with a solution using recursion.

class Array
   def max_sub_array
     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.slice(i+1..(ary.size-1)).max_sub_arrayr
           done = true
         end
       elsif sum <= n
         sub_ary, sum = ary.slice(i..(ary.size-1)).max_sub_arrayr
         done = true
       end
       if sum > max_sum
         max_sum = sum
         max_sub_ary = sub_ary.dup
         break if done
       end
     end
     return max_sub_ary, max_sum
   end
end

Michael Glaesemann
grzm seespotcode net