max subarray (sub array with the greatest sum)

gistfile1.rb

class Array
  def max_subarray_last_index
    max_sum = new_maxium = last_index = 0

    each_with_index do |value, i|
      new_maxium = [new_maxium + value, 0].max

      # update everything if we found a truly new maximum =)
      max_sum, last_index = new_maxium, i if max_sum < new_maxium 
    end

    last_index
  end 

  def max_subarray
    self[size - reverse.max_subarray_last_index - 1..max_subarray_last_index]
  end
end