Leetcode: Maximum Product Subarray

Maximum Product Subarray


<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/maximum-product-subarray“><img align=”right” width=”200″ height=”183″ src=”github.png” /></a>

Similar Problems:


Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],

the contiguous subarray [2,3] has the largest product = 6.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/maximum-product-subarray
// Basic Ideas: presum
// Complexity: Time O(n), Space O(1)
func maxProduct(nums []int) int {
    res := -1 << 31
    for preProd, pmax, nmax, i := 1, 1, -1 << 31, 0; i<len(nums); i++ {
        if nums[i] != 0 {
            preProd = preProd * nums[i]
            if preProd > 0 {
                if res < preProd { res = preProd }
            } else {
                if nmax != -1<<31 {
                    if res < preProd/nmax { res = preProd/nmax }
                } else {
                    if res < preProd/pmax { res = preProd/pmax }
                }
            }
            if preProd > 0 && preProd > pmax { pmax = preProd }
            if preProd < 0 && preProd > nmax { nmax = preProd }
        } else {
            if res < 0 {
                res = 0
            }
            preProd, pmax, nmax = 1, 1, -1 << 31
        }
    }
    return res
}

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.