[LeetCode]152. 乘积最大子数组

题目

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

示例 1:

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

示例 2:

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

解题思路

对于乘法，我们需要注意，负数乘以负数，会变成正数，所以解这题的时候我们需要维护两个变量，当前的最大值，以及最小值，最小值可能为负数，但下一步可能会再乘以一个负数，当前的最大值就变成最小值，而最小值则变成最大值了。

动态方程如下：

maxdp[i + 1] = max(maxdp[i] * nums[i + 1], nums[i + 1],mindp[i] * nums[i + 1])
mindp[i + 1] = min(mindp[i] * nums[i + 1], nums[i + 1],maxdp[i] * nums[i + 1])
dp[i + 1] = max(dp[i], maxdp[i + 1])

考虑优化空间。由于第 i 个状态只和第 i−1 个状态相关，根据「滚动数组」思想，我们可以只用两个变量来维护 i−1 时刻的状态，一个维护 maxdp，一个维护mindp。(这里需要一个临时变量temp存储上一步的maxdp)

temp = maxdp
maxdp = max(temp * nums[i], nums[i], mindp * nums[i])
mindp = min(mindp * nums[i], nums[i], temp * nums[i])
res = max(maxdp, res)

代码

class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
if n==0:
return 0
if n==1:
return nums[0]
res = nums[0]
maxdp = nums[0]
mindp = nums[0]
for i in range(1, n):
temp = maxdp
maxdp = max(temp*nums[i], nums[i], mindp*nums[i])
mindp = min(mindp*nums[i], nums[i], temp*nums[i])
res = max(maxdp, res)
return res

最后

以上就是彪壮大船为你收集整理的[LeetCode]152. 乘积最大子数组的全部内容，希望文章能够帮你解决[LeetCode]152. 乘积最大子数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。