《算法题讲解指南：动态规划算法--子数组系列》--21.乘积最大子数组，22.乘积为正数的最长子数组

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》《C++入门到进阶&自我学习过程记录》
《算法题讲解指南》--优选算法
《算法题讲解指南》--递归、搜索与回溯算法
《算法题讲解指南》--动态规划算法

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

21.乘积最大子数组

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

22.乘积为正数的最长子数组

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

21.乘积最大子数组

题目链接：

152. 乘积最大子数组 - 力扣（LeetCode）

题目描述：

​

题目示例：

​

解法(动态规划)：

算法思路：

这道题与「最大子数组和」非常相似，我们可以效仿着定义一下状态表示以及状态转移：
i.dp[i]表示以i为结尾的所有子数组的最大乘积，
ii. dp[i] = max(nums[i], dp[i - 1] * nums[i]);
由于正负号的存在，我们很容易就可以得到，这样求dp[i]的值是不正确的。因为dp[i-1]的信息并不能让我们得到dp[i]的正确值。比如数组[-2，5，-2]，用上述状态转移得到的dp数组为[-2，5，-2]，最大乘积为5 。但是实际上的最大乘积应该是所有数相乘，结果为20。
究其原因，就是因为我们在求dp[2]的时候，因为nums[2]是一个负数，因此我们需要的是「i -1 位置结尾的最小的乘积(-10)」，这样一个负数乘以「最小值」，才会得到真实的最大值。
因此，我们不仅需要一个「乘积最大值的dp表」，还需要一个「乘积最小值的dp表」。

1.状态表示：
f[i]表示:以i结尾的所有子数组的最大乘积，
g[i]表示:以i结尾的所有子数组的最小乘积。

2.状态转移方程：
遍历每一个位置的时候，我们要同步更新两个dp 数组的值。
对于f[i]，也就是「以为结尾的所有子数组的最大乘积」，对于所有子数组，可以分为下面三种形式：
i.子数组的长度为1，也就是nums[i];
ii.子数组的长度大于1 ，但nums[i]>0，此时需要的是i-1 为结尾的所有子数组的最大乘积f[i-1]，再乘上nums[i]，也就是nums[i]* f[i- 1];
iii.子数组的长度大于1，但nums[i]<0，此时需要的是i-1为结尾的所有子数组的最小乘积g[i-1]，再乘上nums[i]，也就是nums[i]* g[i-1];
(如果nums[i]=0，所有子数组的乘积均为0，三种情况其实都包含了)
综上所述，f[i] = max(nums[i]， max(nums[i]* f[i - 1]， nums[i] * g[i - 1]) ).
对于g[i]，也就是「以i为结尾的所有子数组的最小乘积」，对于所有子数组，可以分为下面三种形式：
i.子数组的长度为1，也就是nums[i];
ii.子数组的长度大于1，但nums[i]>0，此时需要的是i-1为结尾的所有子数组的最小乘积g[i-1]，再乘上nums[i]，也就是nums[i]* g[i-1];
iii.子数组的长度大于1 ，但nums[i]<0 ，此时需要的是i1 为结尾的所有子数组的最大乘积f[i-1]，再乘上 nums[i]，也就是 nums[i] * f[i-1];
综上所述， g[i] = min(nums[i]， min(nums[i] * f[i -1]， nums[i] * g[i - 1]))
(如果nums[i]=0，所有子数组的乘积均为0，三种情况其实都包含了)

3.初始化：
可以在最前面加上一个辅助结点，帮助我们初始化。使用这种技巧要注意两个点:
i.辅助结点里面的值要保证后续填表是正确的;
ii.下标的映射关系。
在本题中，最前面加上一个格子，并且让f[0]=g[0]=1即可。

4.填表顺序：
根据状态转移方程易得，填表顺序为「从左往右，两个表一起填」。

5.返回值：
返回 f 表中的最大值。

C++算法代码：

class Solution { public: int maxProduct(vector<int>& nums) { int n = nums.size(); vector<int> max_dp(n); vector<int> min_dp(n); max_dp[0] = min_dp[0] = nums[0]; for(int i = 1; i < n; i++) { if(nums[i] >= 0) { max_dp[i] = max(max_dp[i - 1] * nums[i], nums[i]); min_dp[i] = min(min_dp[i - 1] * nums[i], nums[i]); } else { max_dp[i] = max(min_dp[i - 1] * nums[i], nums[i]); min_dp[i] = min(max_dp[i - 1] * nums[i], nums[i]); } } int ret = INT_MIN; for(int i = 0; i < n; i++) { ret = max(ret, max_dp[i]); } return ret; } };

算法总结及流程解析：

22.乘积为正数的最长子数组

题目链接：

1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

继续效仿「最大子数组和」中的状态表示，尝试解决这个问题。
状态表示：dp[i]表示「所有以i 结尾的子数组，乘积为正数的最长子数组的长度」。
思考状态转移:对于i位置上的nums[i]，我们可以分三种情况讨论：
i.如果nums[i]=0，那么所有以i为结尾的子数组的乘积都不可能是正数，此时dp[i]=0;
ii.如果nums[i]>0 ，那么直接找到dp[i-1]的值(这里请再读一遍dp[i-1]代表的意义，并且考虑如果dp[i-1]的结值是0 的话，影不影响结果)，然后加1即可，此时dp[i]=dp[i-1]+1;
iii.如果nums[i]<0，这时候你该蛋疼了，因为在现有的条件下，你根本没办法得到此时的最长长度。因为乘法是存在「负负得正」的，单单靠一个dp[i-1]，我们无法推导出dp[i]的值。
但是，如果我们知道「以i-1为结尾的所有子数组，乘积为负数的最长子数组的长度」neg[i-1]，那么此时的dp[i]是不是就等于neg[i-1]+1呢?
通过上面的分析，我们可以得出，需要两个dp表，才能推导出最终的结果。不仅需要一个「乘积为正数的最长子数组」，还需要一个「乘积为负数的最长子数组」。

1.状态表示：
f[i]表示：以i结尾的所有子数组中，乘积为「正数」的最长子数组的长度;
g[i]表示：以i结尾的所有子数组中，乘积为「负数」的最长子数组的长度。

2.状态转移方程：
遍历每一个位置的时候，我们要同步更新两个dp数组的值。
对于f[i]，也就是以i为结尾的乘积为「正数」的最长子数组，根据nums[i]的值，可以分为三种情况：
i.nums[i]=0时，所有以i为结尾的子数组的乘积都不可能是正数，此时f[i]=0;
ii. nums[i] > 0时，那么直接找到f[i - 1]的值(这里请再读一遍f[i-1]代表的意义，并且考虑如果f[i-1]的结值是0的话，影不影响结果)，然后加一即可，此时 f[i]= f[i- 1] + 1;
iii. nums[i]<0时，此时我们要看g[i-1] 的值(这里请再读一遍 g[i-1]代表的意义。因为负负得正，如果我们知道以i-1为结尾的乘积为负数的最长子数组的长度，加上1即可)，根据g[i-1]的值，又要分两种情况：
1. g[i-1]=0 ，说明以i-1 为结尾的乘积为负数的最长子数组是不存在的，又因为nums[i]<0，所以以i 结尾的乘积为正数的最长子数组也是不存在的，此时f[i]=0;
2. g[i - 1] !=0，说明以i-1为结尾的乘积为负数的最长子数组是存在的，又因为nums[i]< 0，所以以i 结尾的乘积为正数的最长子数组就等于g[i-1]+1；
综上所述，nums[i]< 0时，f[i] =g[i-1 == 0 ? 0 : g[i-1] + 1；

对于g[i]，也就是以i为结尾的乘积为「负数」的最长子数组，根据nums[i]的值，可以分为三种情况：
i.nums[i]=时，所有以i为结尾的子数组的乘积都不可能是负数，此时g[i]=0;
ii.nums[i] < 0时，那么直接找到f[i-1]的值(这里请再读一遍f[i-1]代表的意义，并且考虑如果f[i-1]的结值是的话，影不影响结果)，然后加一即可(因为正数*负数=负数)，此时 g[i] = f[i -1]+ 1 ;
iii.nums[i]>0 时，此时我们要看g[i-1]的值(这里请再读一遍 g[i -1]代表的意义。因为正数*负数=负数)，根据g[i-1]的值，又要分两种情况：
1.g[i- 1]= ，说明以i- 1 为结尾的乘积为负数的最长子数组是不存在的，又因为nums[i]>0，所以以i结尾的乘积为负数的最长子数组也是不存在的，此时f[i]=0;
2. g[i-1] != 0 ，说明以i-1 为结尾的乘积为负数的最长子数组是存在的，又
因为nums[i]>0，所以以i 结尾的乘积为正数的最长子数组就等于g[i-1] + 1;
综上所述， nums[i] > 0 时, g[i] = g[i -1 == 0 ? 0 : g[i - 1] + 1 ;

这里的推导比较绕，因为不断的出现「正数和负数」的分情况讨论，我们只需根据下面的规则，严格找到此状态下需要的dp 数组即可：
i.正数* 正数=正数
ii.负数*负数=正数
iii.负数*正数=正数*负数=负数

3.初始化：
可以在最前面加上一个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：
i.辅助结点里面的值要「保证后续填表是正确的」;
ii. 「下标的映射关系」。
在本题中，最前面加上一个格子，并且让f[0]= g[0]= 0即可。

4.填表顺序：
根据「状态转移方程」易得，填表顺序为「从左往右，两个表一起填」。

5.返回值：
根据「状态表示」，我们要返回f 表中的最大值。

C++算法代码：

class Solution { public: int getMaxLen(vector<int>& nums) { int n = nums.size(); vector<int> pos_dp(n); vector<int> neg_dp(n); if(nums[0] > 0) { pos_dp[0] = 1; neg_dp[0] = 0; } else if(nums[0] < 0) { pos_dp[0] = 0; neg_dp[0] = 1; } else { pos_dp[0] = neg_dp[0] = 0; } for(int i = 1; i < n; i++) { if(nums[i] > 0) { pos_dp[i] = pos_dp[i - 1] + 1; neg_dp[i] = neg_dp[i - 1] == 0 ? 0 : neg_dp[i - 1] + 1; } else if(nums[i] < 0) { pos_dp[i] = neg_dp[i - 1] == 0 ? 0 : neg_dp[i - 1] + 1; neg_dp[i] = pos_dp[i - 1] + 1; } else { pos_dp[i] = neg_dp[i] = 0; } } int ret = INT_MIN; for(int i = 0; i < n; i++) { ret = max(ret, pos_dp[i]); } return ret; } };

算法总结及流程解析：

结束语

到此，21.乘积最大子数组，22.乘积为正数的最长子数组 这两道算法题就讲解完了。对于乘积最大子数组问题：采用双DP数组分别记录以i结尾的最大和最小乘积，通过比较当前元素、与前驱最大乘积或最小乘积的组合来递推求解；对于乘积为正数的最长子数组问题：同样使用双DP数组分别记录以i结尾的正数和负数乘积最长子数组长度，根据当前元素正负分情况讨论状态转移。希望大家能有所收获！