动态规划 —— 子数组系列-乘积最大子数组
1. 乘积最大子数组
题目链接：
152. 乘积最大子数组 - 力扣（LeetCode）
https://leetcode.cn/problems/maximum-product-subarray/description/
2. 算法原理
状态表示：以某一个位置为结尾或者以某一个位置为起点
f[i]表示：以i位置为结尾的所有子树中的最大乘积
[i]表示：以i位置为结尾的所有子树中的最小乘积
2. 状态转移方程
f[i]分为两种情况：1. 长度为1 nums[i]
2. 长度大于1分为两种情况：a. nums[i] > 0 nums[i] * f[i-1]
b. nums[i] < 0 nums[i] * g[i-1]
f[i] = max(nums[i] , nums[i] * f[i-1] , nums[i] * g[i-1] )
g[i]分为两种情况：1. 长度为1 nums[i]
2. 长度大于1分为两种情况：a. nums[i] > 0 nums[i] * g[i-1]
b. nums[i] < 0 nums[i] * f[i-1]
g[i] = min(nums[i] , nums[i] * f[i-1] , nums[i] * g[i-1] )
nums[i]等于0并不影响结果，所以不用讨论
3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行
我们可以在左边加上一个虚拟节点，因为本题并不是加减而是乘，所以为了不影响最终结果就可以把这个虚拟节点初始化为1
本题的下标映射关系：下标统一往右移动一位
4. 填表顺序
本题的填表顺序是：从左往右，两个表一起填
5. 返回值 ：题目要求 + 状态表示
本题的返回值是：f表里的最大值
3. 代码
动态规划的固定四步骤：1. 创建一个dp表
2. 在填表之前初始化
3. 填表（填表方法：状态转移方程）
4. 确定返回值
class Solution {
public:
int maxProduct(vector<int>& nums) {
//1. 创建一个dp表
int n=nums.size();
vector<int>f(n+1),g(n+1);
//2. 在填表之前初始化
f[0]=g[0]=1;
//3. 填表（填表方法：状态转移方程）
//因为返回值是返回f表里的最大值，所以先定义一个变量记录一下最终结果
int ret=INT_MIN;//因为要求最大值，所以定义无穷小
for(int i=1;i<=n;i++)
{
//先将三种状态放到三个临时变量里
//因为加了一个虚拟节点，所下标要-1
int x=nums[i-1],y=f[i-1]*nums[i-1],z=g[i-1]*nums[i-1];
f[i]=max(x,max(y,z));
g[i]=min(x,min(y,z));
ret=max(ret,f[i]);
}
//4. 确定返回值
return ret;
}
};未完待续~
原文地址：https://blog.csdn.net/hedhjd/article/details/143788844
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！