动态规划 —— 子数组系列-乘积最大子数组

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;
    }
};

未完待续~