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

1.题目解析

题目来源：152.乘积最大子数组——力扣

测试用例

2.算法原理

1.状态表示

由于题目给的数组中可以包含负数，因此求最大乘积有两种情况：

a.负数乘以最小数得出最大乘积 b.整数乘以最大数得出最大乘积

所以需要两个表分别求出最大最小数，即创建f表存储最大数，g表存储最小数

f[i]:从开始位置到第i个位置的最大子数组乘积

g[i]:从开始位置到第i个位置的最小子数组乘积

2.状态转移方程

f[i]=max(nums[i-1],nums[i-1]*f[i-1],nums[i-1]*g[i-1])

g[i]=min(nums[i-1],nums[i-1]*f[i-1],nums[i-1]*g[i-1])

3.初始化

根据状态转移方程可知每个位置都需要用到前一个位置来进行计算，因此需要初始化两个表的第一个位置，这里更加简单的是使用一个虚拟位置，因为是乘积计算所以将虚拟位置赋值为1不会影响后续填表

4.填表顺序

从前向后，两个表一起填写

5.返回值

返回f表中的最大值即可

3.实战代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        vector<int> g(n + 1);

        f[0] = g[0] = 1;
        int ret = INT_MIN;

        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int y = f[i - 1] * nums[i - 1];
            int 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]);
        }

        return ret;
    }
};