乘积最大子数组

1. 题目描述

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

2. 思路

1. 思路一
   • 暴力
   • 两层for循环计算出最大的乘积
2. 思路二
   • 类似最大子序和.md，不过得考虑负数，由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin

3. 实现

3.1. 暴力

func maxProduct(nums []int) int {
	max := math.MinInt32
	for i := 0; i < len(nums); i++ {
		res := 1
		for j := i; j < len(nums); j++ {
			res *= nums[j]
			max = Max(max, res)
		}
	}

	return max
}

3.2. 试探

func maxProduct(nums []int) int {
    res := nums[0]
    minVal := 1
    maxVal := 1
    for _, num := range nums {
        if num < 0 {
            maxVal,minVal = minVal,maxVal
        }
        maxVal = max(maxVal*num, num)
        minVal = min(minVal*num, num)
        res = max(maxVal, res)
    }
    return res
}

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

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

4. 参考

• 152. 乘积最大子数组 - 力扣（LeetCode）
• 回溯（递归）、动态规划两种算法求解乘积最大子序列 - 乘积最大子数组 - 力扣（LeetCode）
• 画解算法：152. 乘积最大子序列 - 乘积最大子数组 - 力扣（LeetCode）