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

本文主要是介绍「动态规划」如何求乘积最大子数组？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这篇关于「动态规划」如何求乘积最大子数组？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---