跳转至

LC152 - 乘积最大子数组

MaximumProductSubarray.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
package DP

func maxProduct(nums []int) int {
    size := len(nums)
    dpMin := make([]int, size)
    dpMax := make([]int, size)
    dpMin[0] = nums[0]
    dpMax[0] = nums[0]
    ans := dpMax[0]
    for i := 1; i < size; i++ {
        dpMin[i] = min(nums[i], dpMin[i-1]*nums[i], dpMax[i-1]*nums[i])
        dpMax[i] = max(nums[i], dpMax[i-1]*nums[i], dpMin[i-1]*nums[i])
        ans = max(ans, dpMax[i])
    }
    return ans
}