152. 乘积最大子数组
https://leetcode.cn/problems/maximum-product-subarray/description/
给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个32位整数。
- 输入：nums = [2,3,-2,4]，输出：6，解释：子数组[2,3]有最大乘积6。
- 输入：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()));
}
};
