当前位置：首页 > article >正文

乘积最大子数组

article 2024/12/2 1:08:44

乘积最大子数组

给你一个整数数组 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-位 整数

题解：

如果我们用 dp (i) 开表示以第 i 个元素结尾的乘积最大子数组的乘积，a 表示输入参数 nums，那么根据「53. 最大子序和」的经验，我们很容易推导出这样的状态转移方程：

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

得到如下的代码：

func maxProduct(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    maxx := nums[0]
    for i:=1; i < len(nums); i++ {
        dp[i] = max(dp[i-1] * nums[i], nums[i])
        if maxx < dp[i] {
            maxx = dp[i]
        }
    }
	return maxx
}

但是，在这里，这样做是错误的。因为出现负数，负负得正会使得我们的最大值的子问题分解是错误的，解决方法呢是我们需要同时记录最小值，将最小值与当前元素的乘积放在比较选项之中

func maxProduct(nums []int) int {
	MAXX := make([]int, len(nums))
	MINN := make([]int, len(nums))
	MAXX[0], MINN[0] = nums[0], nums[0]
	maxx, minn := nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
        MAXX[i] = max(nums[i], max(MAXX[i-1] * nums[i], MINN[i-1] * nums[i]))
        MINN[i] = min(nums[i], min(MINN[i-1] * nums[i], MAXX[i-1] * nums[i]))
		if maxx < MAXX[i] {
			maxx = MAXX[i]
		}
        if minn < MINN[i] {
			minn = MINN[i]
		}
	}
	return maxx
}