「动态规划」如何求乘积最大子数组？

152. 乘积最大子数组https://leetcode.cn/problems/maximum-product-subarray/description/

给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个32位整数。

1. 输入：nums = [2,3,-2,4]，输出：6，解释：子数组[2,3]有最大乘积6。
2. 输入：nums = [-2,0,-1]，输出：0，解释：结果不能为2，因为[-2,-1]不是子数组。

提示：1 <= nums.length <= 2 * 10^4，-10 <= nums[i] <= 10，nums的任何前缀或后缀的乘积都保证是一个32位整数。

---

我们用动态规划的思想来解决这个问题。

确定状态表示：根据经验和题目要求，我们可以选择用dp[i]表示，以i位置为结尾的所有子数组中，最大的乘积。比如，dp[3]就表示：下标范围在[0, 3]，[1, 3]，[2, 3]，[3, 3]这4个子数组中，最大的乘积。但是这样的状态表示是推不出状态转移方程的，因为被乘数和乘数的正负也会影响到乘积的大小，比如2个很小的负数相乘的结果会很大（-1000 x -1000 = 1000000）。所以，我们还需要定义一个保存最小乘积的状态表示，也就是说：

• 用f[i]表示，以i位置为结尾的所有子数组中，最大的乘积。
• 用g[i]表示，以i位置为结尾的所有子数组中，最小的乘积。

推导状态转移方程：考虑f[i]，即以i位置为结尾的所有子数组中最大的乘积，分类讨论以下情况：

• 如果子数组的长度为1，也就是说子数组的下标范围是[i, i]，那么最大的乘积就是nums[i]本身。
• 如果子数组的长度大于1，最大的乘积就和nums[i]的正负相关。
  • 如果nums[i]是正数，那么子数组中除了nums[i]的其他元素的乘积越大，子数组的乘积就越大（因为y = kx，k > 0时是增函数，x越大，y越大）。也就是说，此时最大的乘积就是以i - 1位置为结尾的所有子数组中的最大的乘积乘以nums[i]，即f[i - 1] * nums[i]。
  • 如果nums[i]是负数，那么子数组中除了nums[i]的其他元素的乘积越小，子数组的乘积就越大（因为y = kx，k < 0时是减函数，x越小，y越大）。也就是说，此时最大的乘积就是以i - 1位置为结尾的所有子数组中的最小的乘积乘以nums[i]，即g[i - 1] * nums[i]。

事实上，乘积的最大值一定是nums[i]，f[i - 1] * nums[i]，g[i - 1] * nums[i]这三者之一，所以f[i] = max(nums[i], f[i - 1] * nums[i], g[i - 1] * nums[i])。乘积的最小值同理，即g[i] = min(nums[i], f[i - 1] * nums[i], g[i - 1] * nums[i])。

初始化：根据状态转移方程，计算f[0]和g[0]时会越界，所以要对其初始化。根据状态表示，f[0]和g[0]分别表示以0为结尾的所有子数组中，乘积的最大值和最小值，显然以0为结尾的子数组只有下标范围是[0, 0]的数组本身，所以f[0] = g[0] = nums[0]。

填表顺序：根据状态转移方程，f[i]和g[i]都依赖于f[i - 1]和g[i - 1]，所以应从左往右，同时填f表和g表。

返回值：由于并不确定子数组结尾的下标，根据状态表示，应返回f表的最大值。

细节问题：f表和g表的规模和nums相同，都是1 x n。

时间复杂度：O(N)，空间复杂度：O(N)。

但是以下代码会有一个测试用例通不过……

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
 
        // 创建dp表
        vector<int> f(n);
        auto g = f;
 
        // 初始化
        f[0] = g[0] = nums[0];
 
        // 填表
        for (int i = 1; i < n; i++) {
            int x = nums[i];
            int y = f[i - 1] * x;
            int z = g[i - 1] * x;
 
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
        }
 
        // 返回结果
        return *max_element(f.begin(), f.end());
    }
};

通不过的测试用例：[0,10,10,10,10,10,10,10,10,10,-10,10,10,10,10,10,10,10,10,10,0]，报错：Line 17: Char 30: runtime error: signed integer overflow: 1000000000 * -10 cannot be represented in type 'int' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior solution.cpp:17:30

溢出了？好好好，这么玩是吧。仔细想想，题目描述中说了：nums的任何前缀或后缀的乘积都保证是一个32位整数，好像没毛病？因为第一个数和最后一个数是0，那么nums的任何前缀或后缀的乘积都是0。好一个文字游戏！

我试着把int改成long long，如下：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
 
        // 创建dp表
        vector<long long> f(n);
        auto g = f;
 
        // 初始化
        f[0] = g[0] = static_cast<long long>(nums[0]);
 
        // 填表
        for (int i = 1; i < n; i++) {
            long long x = static_cast<long long>(nums[i]);
            long long y = f[i - 1] * x;
            long long z = g[i - 1] * x;
 
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
        }
 
        // 返回结果
        return static_cast<int>(*max_element(f.begin(), f.end()));
    }
};

结果同样的测试用例：[0,10,10,10,10,10,10,10,10,10,-10,10,10,10,10,10,10,10,10,10,0]，报错：Line 18: Char 36: runtime error: signed integer overflow: -1000000000000000000 * 10 cannot be represented in type 'long long' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior solution.cpp:18:36

！！？long long还能溢出，活久见！最后改用double，就过了。这个测试用例有毒吧。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
 
        // 创建dp表
        vector<double> f(n);
        auto g = f;
 
        // 初始化
        f[0] = g[0] = static_cast<double>(nums[0]);
 
        // 填表
        for (int i = 1; i < n; i++) {
            double x = static_cast<double>(nums[i]);
            double y = f[i - 1] * x;
            double z = g[i - 1] * x;
 
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
        }
 
        // 返回结果
        return static_cast<int>(*max_element(f.begin(), f.end()));
    }
};