子数组的最大乘积

子数组的最大乘积

读前福利，送大家一些电子书

LeetCode 152. 乘积最大子数组

问题描述

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

示例：

输入：[2,3,-2,4]

输出：6

说明：子数组 [2,3] 有最大乘积 6。

分析问题

这道题和求子数组的最大和很像，建议大家先去看53. 最大子序和。这里我们假设以第i个数结尾的连续子数组的最大乘积为f_max(i)，对于以第i个数结尾的子数组来说，因为nums[i]有可能是正数，也有可能是负数，需要分两种情况来讨论。

1. 如果nums[i]为整数，那么f_max(i)要么等于nums[i]，要么等于f_max(i-1) * nums[i]，即f_max(i)=max(nums[i],f_max(i-1)+nums[i])。
2. 如果nums[i]为负数，那么f_max(i)要么等于nums[i]，要么等于以它前一个位置结尾的最小值和nums[i]的乘积，因为一个负数乘以一个最小值，它的结果反而大。这里我们假设以第i个数结尾的连续子数组的最小乘积为f_min(i)，因此可以得出f_max(i)=max(nums[i], f_min(i-1) *nums[i])。

综上所述，对于以第i个数结尾的连续子数组来说，我们需要维护两个状态，即最大乘积f_max(i)和最小乘积f_min(i)，且状态转移方程为：

​ f_max(i) = max {f_max(i-1) * nums[i] , nums[i] , f_min(i-1) * nums[i]}

​ f_min(i) = min {f_min(i-1) * nums[i], nums[i] , f_max * nums[i]}

下面我们来看一下代码的实现。

class Solution:
    def maxProduct(self,nums):
        n=len(nums)
        dp_max=nums[:]
        dp_min=nums[:]
        for i in range(1,n):

            dp_max[i]=max(nums[i],dp_min[i-1] * nums[i],dp_max[i-1] * nums[i])
            dp_min[i]=min(nums[i],dp_min[i-1] * nums[i],dp_max[i-1] * nums[i])

        return max(dp_max)

该算法的时间复杂度和空间复杂度都是O(n)。由于第i个状态只有i-1的状态有关，所以我们不需要保存i-1之前的状态，因为我们只需要常数个变量就可以求解，如下所示。

class Solution:
    def maxProduct(self,nums):
        n=len(nums)
        dpmax=nums[0]
        dpmin=nums[0]
        res=nums[0]
        for i in range(1,n):
            tmpmax=dpmax
            tmpmin=dpmin

            dpmax=max(nums[i], tmpmin * nums[i], tmpmax * nums[i])
            dpmin=min(nums[i], tmpmin * nums[i], tmpmax * nums[i])
            res=max(dpmax,res)

        return res

该算法的时间复杂度是O(n)，空间复杂度是O(1)。