From: Will Bailey <will.bailey@...>
Date: 2007-07-16T00:40:05+09:00
Subject: [QUIZ][SOLUTION] Maximum Sub-Array (#131)

------=_Part_18227_22633237.1184514005116
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Here is my solution.  I extended Array to have a max_slice method.  It first
checks if the array is all positives returning the array minus any zeros if
so.  Then it checks to see if the array is all negative or zero returning
the max value if so.  If both of these checks fail, it does an exhaustive
search of the array storing the sum of each contiguous sub-array as the key
in a hash with the value being the sub-array.  I thought I was being a bit
clever by joining the array with pluses and then calling eval to get the
sum...but maybe this is not a good practice.  Let me know what you think.

-Wb

class Array
  def max_slice
    return self-[0] if select{|k|k<0}.size==0
    return [max] if select{|k|k>=0}.size==0
    p={}
    each_with_index do |o,i|
      i.upto(size-1) do |j|
        p[eval(slice(i..j).join("+"))] = slice(i..j)
      end
    end
    p.max[1]
  end
end

puts [-1, 2, 5, -1, 3, -2, 1].max_slice.inspect

# describe Array do
#   it "should return the max slice" do
#     input = [-1, 2, 5, -1, 3, -2, 1]
#     input.max_slice.should == [2, 5, -1, 3]
#   end
# end

------=_Part_18227_22633237.1184514005116--