LeetCode152. 乘积最大子数组（2024秋季每日一题 2）

本文主要是介绍LeetCode152. 乘积最大子数组（2024秋季每日一题 2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个整数数组 $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\ast 10^4$
$-10<=nums[i]<=10$
$nums$ 的任何子数组的乘积都 保证 是一个 $32$-位 整数

---

方法一：暴力：$O(N^2)$

能过的样例数：$187/190$

思路：第一层循环枚举子数组长度，第二层循环枚举子数组区间左边的索引，并且维护一个滑动窗口，用于记录窗口内的乘积值。

class Solution {
public:int maxProduct(vector<int>& nums) {int res = -20;for(int len = 1; len <= nums.size(); len++){int x = 1, l = -1;for(int j = 0; j <= len - 1; j++){if(x == 0) x = nums[j];else x *= nums[j];if(nums[j] == 0) l = j;}res = max(res, x);for(int i = 1; i + len - 1 < nums.size(); i++){if(x == 0) x = nums[i + len - 1];else {if(nums[i + len - 1] == 0) l = i + len - 1;if(nums[i-1] != 0 && i > l){x = x / nums[i-1] * nums[i + len - 1];}else{x = x * nums[i + len - 1];}}res = max(res, x);}}return res;}
};

方法二：DP：$O(N)$

思路：维护三个数，res、imax、imin

• 遍历数组时维护当前子数组的最大值、最小值
• 当遇到负数时，最大值，最小值交换
• 当遇到0时，imax，imin 重置，在子数组内重新计算

注意：这里的子数组指的是 以 0 为分割的子数组

$imax=max(nums[i],imax\ast nums[i])$
$imin=min(nums[i],imin\ast nums[i])$

当乘给 负数 时，imin 与 imax 交换（最大，最小值交换）

class Solution {
public:int maxProduct(vector<int>& nums) {int res = -20, imin = 1, imax = 1;for(int i = 0; i < nums.size(); i++){if(nums[i] < 0) swap(imin, imax);imax = max(imax * nums[i], nums[i]);imin = min(imin * nums[i], nums[i]);res = max(res, imax);}return res;}
};

这篇关于LeetCode152. 乘积最大子数组（2024秋季每日一题 2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---