LeetCode-热题100：152. 乘积最大子数组
题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
- 1 <= nums.length <= 2 * 104
- -10 <= nums[i] <= 10
- nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
（动态规划）代码及注释
func maxProduct(nums []int) int {// 初始化最大乘积、最小乘积和结果为数组的第一个元素maxProduct, minProduct, result := nums[0], nums[0], nums[0]// 遍历数组，从第二个元素开始for i := 1; i < len(nums); i++ {// 如果当前数字是负数，交换最大乘积和最小乘积if nums[i] < 0 {maxProduct, minProduct = minProduct, maxProduct}// 计算当前位置的最大乘积和最小乘积maxProduct = max(nums[i], maxProduct * nums[i])minProduct = min(nums[i], minProduct * nums[i])// 更新结果，取当前的最大乘积和之前的结果中的较大值result = max(result, maxProduct)}// 返回最大乘积return result
}// 辅助函数，返回两个整数中的较大值
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
}
代码解释
1.使用 maxVal 和 minVal
在这个问题中，乘积的最大值或最小值可能会受到负数的影响。因此，我们需要维护两个变量：maxVal 和 minVal。
maxVal: 维护以当前元素为结尾的子数组的最大乘积。minVal: 维护以当前元素为结尾的子数组的最小乘积。
2.当遇到负数时
当遇到负数时，最大值和最小值会互相交换，因为负数乘以一个负数会变成正数，可能会变得更大。
3.更新 maxVal 和 minVal
-
maxVal = max(nums[i], maxVal * nums[i]): 对于当前元素nums[i]，我们比较它和maxVal * nums[i]的乘积，取其中的最大值。 -
minVal = min(nums[i], minVal * nums[i]): 同样地，我们比较当前元素nums[i]和minVal * nums[i]的乘积，取其中的最小值。
4.更新结果
- 每次更新
maxVal后，我们都需要更新全局结果res。
（暴力）代码及注释
func maxProduct(nums []int) int {// 初始化结果为最小整数值res := math.MinInt32// 外部循环遍历数组for i := 0; i < len(nums); i++ {// 初始化临时乘积为1tmp := 1// 内部循环计算从 i 开始到数组末尾的连续子数组的乘积for j := i; j < len(nums); j++ {tmp *= nums[j]// 更新结果res = max(tmp, res)}}// 返回结果return res
}// 辅助函数，返回两个整数中的较大值
func max(a, b int) int {if a > b {return a}return b
}
代码解释
1.使用 res 初始化为 math.MinInt32
- 初始化
res为math.MinInt32是为了保证结果能够正确地被更新。如果数组nums中的所有元素都是非正数，那么最大乘积应该是math.MinInt32。
2.使用双重循环计算乘积
- 外部循环从数组的第一个元素开始，内部循环从外部循环的当前位置开始，计算从当前位置到数组末尾的连续子数组的乘积。
3.更新 res
- 在计算每一个连续子数组的乘积时，我们都会更新
res，确保它始终保存着乘积的最大值。
优点和缺点
优点：
- 这个方法非常直观，通过双重循环穷举了所有可能的连续子数组。
缺点：
-
时间复杂度较高，为 (O(n^2))，其中 (n) 是数组的长度。
-
空间复杂度为 (O(1))。
这个方法虽然直观，但由于时间复杂度较高，对于大规模的数据可能会导致性能问题。