152.乘积最大子数组

动态规划

考虑当前数字为正还是为负，并维护前序乘积最大和最小数组。

由于当前位置乘积最大值只与前一位置的乘积最大值或最小值有关，则可以优化数组为两个变量。

时间复杂度： O(N)
空间复杂度： O(1)

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

func max(a, b int) int {
    if (a > b) {
        return a
    }
    
    return b
}

func min(a, b int) int {
    if (a < b) {
        return a
    }
    
    return b
}