A ruby divide & conquer solution


  • 0
    L

    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
    

  • 0
    L

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


Log in to reply
 

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