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