# A ruby divide & conquer solution

• Until to now, I find no one show the divide & conquer solution, so I give one. It might be a little complicated, but I think it is more delicate. It is coded with ruby, but easy to understand.

``````# https://github.com/lixianmin/leetcode/tree/master/algorithms/maximum-product-subarray

def do_max_product (data, _begin, _end)
return data[_begin], data[_begin] if _end - _begin == 1

mid = (_begin + _end)/2
lmin, lmax = do_max_product(data, _begin, mid)
rmin, rmax = do_max_product(data, mid, _end)

mymin = lmin < rmin ? lmin : rmin
mymax = lmax > rmax ? lmax : rmax

temp = data[mid-1]
lmin, lmax = temp, temp
(mid-2).downto(_begin) do |i|
temp *= data[i]
if temp < lmin
lmin = temp
elsif temp > lmax
lmax = temp
end
end

temp = data[mid]
rmin, rmax = temp, temp
(mid+1).upto(_end-1) do |i|
temp *= data[i]
if temp < rmin
rmin = temp
elsif temp > rmax
rmax = temp
end
end

return [mymin, mymax, lmin*rmin, lmin*rmax, lmax*rmin, lmax*rmax].minmax
end

def max_product(nums)
return 0 if !nums or nums.length <= 0
_, max = do_max_product(nums, 0, nums.length)
max
end
``````

• Ok, my bad, I find several other divide-and-conquer solutions, may be I need to do more research = =

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.