152. Maximum Product Subarray

Medium

Given an integer array nums, find a

subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,3,-2,4]
Output:
 6
Explanation:
 [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output:
 0
Explanation:
 The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

• 1 <= nums.length <= 2 * 104

• -10 <= nums[i] <= 10

• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

解題

使用兩個陣列儲存當前包含前一個元素的最大 / 最小子數列。

最大可能是 目前的單個元素、最大子數列*當前元素(若當前元素為正數)、最小子數列*當前元素(若當前元素為負數)

Runtime: 4 ms, faster than 93.98%

Memory Usage: 6.7 MB, less than 6.54%

func maxProduct(nums []int) int {
    // min := nums[0]
    res := nums[0]
    dp1 := []int{nums[0]}
    dp2 := []int{nums[0]}

    for i:=1; i<len(nums); i++ {
        dp1 = append(dp1, max(nums[i], dp1[i - 1] * nums[i], dp2[i - 1]* nums[i]))
        dp2 = append(dp2, min(nums[i], dp2[i - 1] * nums[i], dp1[i - 1]* nums[i]))

        if dp1[i] > res {
            res = dp1[i]
        }
    }

    return res
}

func max(a, b, c int) int {
    if a >= b && a >= c {
        return a
    } else if b >= a && b >= c{
        return b
    } 
    
    return c
}

func min(a, b, c int) int {
    if a <= b && a <= c {
        return a
    } else if b <= a && b <= c{
        return b
    } 
    
    return c
}

精簡版，把兩個陣列變成兩個變數

Runtime: 4 ms, faster than 93.98%

Memory Usage: 3.3 MB, less than 100%

func maxProduct(nums []int) int {
    res := nums[0]
    maxx := nums[0]
    minn := nums[0]

    for i:=1; i<len(nums); i++ {
        premax := maxx
        maxx =  max(nums[i], maxx * nums[i], minn* nums[i])
        minn =  min(nums[i], minn * nums[i], premax* nums[i])

        if maxx > res {
            res = maxx
        }
    }
    

    return res
}

func max(a, b, c int) int {
    if a >= b && a >= c {
        return a
    } else if b >= a && b >= c{
        return b
    } 
    
    return c
}

func min(a, b, c int) int {
    if a <= b && a <= c {
        return a
    } else if b <= a && b <= c{
        return b
    } 
    
    return c
}