乘积最大子数组

题目描述：

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路:

动态规划做，需要额外一个dp_min数组，用于放最小数，是为了考虑两个负数乘变成正数的情况。

dp_min[i] = min(min(dp_min[i-1]*nums[i],dp_max[i-1]*nums[i] ),nums[i])

dp_max[i] = max(max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i]),nums[i])

res = max(res,dp_max[i])

代码:

func maxProduct(nums []int) int {
    if len(nums)==1{
        return nums[0]
    }
    var res int
    dp_min := make([]int, len(nums))
    dp_max := make([]int, len(nums))
    dp_max[0] = nums[0]
    dp_min[0] = nums[0]
    res = dp_max[0]
    for i:=1;i<len(nums);i++{
        dp_min[i] = min(min(dp_min[i-1]*nums[i],dp_max[i-1]*nums[i] ),nums[i])
        dp_max[i] = max(max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i]),nums[i])
        res = max(res,dp_max[i])
    }

    return res
}

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

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

代码效率：

执行用时：4 ms, 在所有 Go 提交中击败了80.65%的用户
内存消耗：3.8 MB, 在所有 Go 提交中击败了15.50%的用户