152. Maximum Product Subarry

题目

一个整数数组 nums，找到一个连续字串，使得乘积最大。

解析

无论是求最大连续加法，还是最大连续乘法，关键在于建立一个 dp 数组，该数组的含义是，包含该元素在内的最大乘积。
那么 dp[i] 就等于 max(dp[i-1]*nums[i]， nums[i])。因为乘法的特殊性，还应记录一个包含该元素的最小值。因为负负可能得正。

dp[i] = max(dp[i-1]nums[i], dm[i-1]nums[i], num[i])
dpm[i] = min(dp[i-1]nums[i], dm[i-1]nums[i], nums[i])

伪代码

for i := range nums
  dp[i] = max(dp[i-1]*nums[i], dm[i-1]*nums[i], num[i])
  dm[i] = min(dp[i-1]*nums[i], dm[i-1]*nums[i], nums[i])
return max(dp)

代码

func maxProduct(nums []int) int {
    dmax := make([]int, len(nums)+1)
    dmin := make([]int, len(nums)+1)
    
    dmax[0] = 1
    dmin[0] = 1
    for i := range nums {
        dmax[i+1] = max(dmax[i]*nums[i], dmin[i]*nums[i], nums[i])
        dmin[i+1] = min(dmax[i]*nums[i], dmin[i]*nums[i], nums[i])
    }
    
    rst:=dmax[1]
    for i:=1; i<len(dmax); i++ {
        if dmax[i] > rst {
            rst = dmax[i]
        }
    }
    return rst
}

func max(a,b,c int) int {
    if a < b {
        a = b
    }
    if a < c {
        a = c
    }
    return a
}

func min(a,b,c int)int {
    if a > b {
        a = b
    }
    if a > c {
        a = c
    }
    return a
}

image.png