题目
给你一个整数数组
nums
,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。示例 1:
1
2
3 输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。示例 2:
1
2
3 输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
审题
关键词:乘积最大、连续子数组(非空)、返回乘积
分析
这是一个求最优解问题,暴力法一定是遍历所有连续子数组取最大乘积。与最大子序和类似,这个问题可以拆分为具有最优结构的子问题。对于一个以当前元素为末尾的数组,如何取得该数组以该元素结尾的子数组的最大积:需要比较当前元素$Val_i$与将当前元素合并的积$Val_i*maxProduct(i-1)$的大小取大者,并判断是否为全局最大值。
值得注意的是,这里我们并不需要考虑不以当前元素为结尾的子数组的积,因为这个数组已经包含在前面的子问题当中,不需要重复考虑。
因此,我们所做的是每一步求得一个局部最大值,并更新全局最大值。
然而考虑到[-1, 2]
这个例子,上述算法会比较2与-2,并取2,丢掉了-2,这似乎没有什么问题;而考虑[-1, 2, -3]
这个例子,如果第一步我们取了2,就会丢掉6这个最大值。所以我们必须考虑:由于一个元素可能为负数,前一个元素为结尾的连续子数组最大积可能会适得其反,给我们最小的结果,所以对动态规划的每一步,我们必须同时保存正数最大值和负数最小值的结果,如果没有其中之一就取为0。
测试用例
1 | [2,3,-2,4] |
动态规划
状态转移方程:
$$
localmaxP(i)=max(localmaxP(i),localmaxP_p(i-1)*V_i,localmaxP_n(i-1))
$$
$$
globalmaxP=max(localmaxP(i-1),~localmaxP(i))
$$
技巧:最大值与最小值与当前元素符号有关,为负则交换;
代码:
1 | class Solution { |
- 时间复杂度$O(N)$
- 空间复杂度 $O(1)$