152。积最大子数组题目来源：https://leetcode-cn.com/problems/maximum-product-subarray/题目给你一个整数数组nums，请find数组中积最大的连续子数组（子数组包含在至少一个数），返回子数组对应的积。示例1：输入：[2,3,-2,4]输出：6解释：子数组[2,3]的最大乘积为6。示例2：输入：[-2,0,-1]输出：0解释：结果不能为2，因为[-2,-1]不是子数组。解题思路：这个动态规划问题和之前的[53.最大子序列和]问题，但是这里要求的是乘积的最大值。因为要求两道题是连续的，所以这里，我们可以这样设计状态，即以nums[i]结尾的连续子数组的最大值。下面我们来看看如何设计状态，推导状态转移方程，然后实现。因为数组中有负数，乘积有可能由大变小，同样，小的也有可能变成大的。这里有一些警告。现在先做状态设计：d[i][j]：表示以nums[i]结尾的连续子数组的最大值。这里，j决定是计算最大值还是最小值。其中，当j=0时，表示计算为最小值，当j=1时，表示计算为最大值。现在推导状态转移方程：因为是乘积关系，nums[i]的正负值与前一个状态值有关，如下：当nums[i]>0时：最大值的乘积为still最大值和最小值的乘积仍然是最小值。当nums[i]<0时：最大值的乘积变为最小值。最小值的乘积成为最大值。当nums[i]=0时，不管最大值最小值，最后的结果都是0，这里其实可以结合以上任何一种情况。但是还是有需要注意的地方。这里前一个状态值的正负也会影响最终的最大值。如果之前的最大值是负数，即dpi-1<0，但这是nums[i]>0的情况，这里我们要重新考虑，此时的最大值应该是dpi=nums[我]。根据这个思路，写出所有情况的状态转移方程，如下：dp[i][0]=min(nums[i],dp[i-1][0]*nums[i])ifnums[i]>=0dp[i][1]=max(nums[i],dp[i-1][1]*nums[i])如果nums[i]>=0dp[i][0]=min(nums[i],dp[i-1][1]*nums[i])如果nums[i]<0dp[i][1]=max(nums[i],dp[i-1][0]*nums[i])ifnums[i]<0具体代码实现如下。代码实现类解决方案：defmaxProduct(self,nums:List[int])->int:iflen(nums)==0:return0length=len(nums)#初始化#dp数组有两个元素，一个为storage最大值，最小值dp=[[0]*2for_inrange(length)]#初始化数组第一个元素为最大值和最小值dp[0][0]=nums[0]dp[0][1]=nums[0]# 开始遍历foriinrange(1,length):#状态转移方程ifnums[i]>0:dp[i][0]=min(nums[i],dp[i-1][0]*nums[i])dp[i][1]=max(nums[i],dp[i-1][1]*nums[i])否则：dp[i]][0]=min(nums[i],dp[i-1][1]*nums[i])dp[i][1]=max(nums[i],dp[i-1][0]*nums[i])#因为最后要取最大值，所以在dp[i][1]中求最大值#初始化返回值res=dp[0][1]foriinrange(1,length):res=max(res,dp[i][1])returnres实现结果以上是使用动态规划，根据题意设计状态，推导出t状态转移方程，用代码实现，然后解决问题《152. 乘积最大子数组》的主要内容。欢迎关注微信公众号《书所集录》
