From: Todd Benson <caduceass@...>
Date: 2007-07-16T00:56:44+09:00
Subject: Re: [QUIZ] Maximum Sub-Array (#131)

Just like many others, I went for brute force with some readability.
Golf solution at the bottom.


class Array
  def sum
    inject {|sum, elem| sum + elem}
  end
  def sub_arrays
    subs = []
    0.upto(size-1) { |i| i.upto(size-1) { |j| subs << self[i..j] } }
    subs
  end
end

foo = Array.new(42) { rand(42) - 21 }  # build array; choice of
numbers here is arbitrary
p foo << "\n"  # show the array
# now show maximum sub-array ...
p foo.sub_arrays.inject([foo.max]) { |max, elem| elem.sum > max.sum ?
elem : max }


Golf solution (3 lines, 120 chars not including array initialization).
 I'm sure it could be shorter, though :(

a = Array.new(42){rand(42)-21}

v=[]
0.upto(b=a.size-1){|i|i.upto(b){|j|v<<a[i..j]}}
p v.inject([a.max]){|z,m|z.inject{|s,i|s+i}>m.inject{|s,i|s+i}?z:m}


Todd