AlgoPressAppearance
0152-乘积最大子数组
https://leetcode.cn/problems/maximum-product-subarray/
给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释:子数组 [2,3] 有最大乘积 6。 示例 2:
输入: [-2,0,-1]
输出: 0
解释:结果不能为 2, 因为 [-2,-1] 不是子数组。
解题思路1: 参考最大子序和，考虑符号(imax,imin交换)
这道题可以参考 0053-最大子序和，但是需要注意的是，乘积中有负数的存在，会归为最小，但是如果两个负数相乘，结果为整数，可能又是一个大叔。 如 【-2,3,-4】 结果不是3，而是 -2 * 3 * -4 = 24。 因此，我们处理在记录最大值的同时，还需要记录最小值。 在遍历到 nums[i] 时，
- 如果 nums[i] 是正数，则正常处理 maxValue = max(maxValue * nums[i], nums[i])
- 如果 nums[i] 是负数，那么乘积最大值将变为最小值，最小值将变为最大值，因此交换当前的 maxValue 和 minValue，再和当前值相乘，就会得到正确的最大值和最小值
参考代码 imax and imin
csharp
public class Solution {
public int MaxProduct(int[] nums) {
if(nums.Length == 0){
return 0;
}
int max = nums[0];
int imax = nums[0]; //保存最大
int imin = nums[0]; //保存最小
for(int i=1; i<nums.Length; i++){
if(nums[i] < 0){
//当nums[i]为负数的时候，那么会导致乘积最大的变成最小的，最小的变成最大的，因此先交换一下，他们继续乘积会得到正确的结果
//imin 起作用就在此刻
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.Max(imax * nums[i], nums[i]);
imin = Math.Min(imin * nums[i], nums[i]);
max = Math.Max(max,imax);
}
return max;
}
}
解题思路2:从0分隔考虑负数个数
当数组中没有0的时候，分为两种情况：
- 当负数个数为偶数的时候，则整个数组的各个数值线程就是最大值。
- 当负数个数为奇数的时候，从左边乘到最后一个负数停止有一个最大值(再往下乘都是负数)，从右边开始往左乘也有一个最大值，取其中的最大值(再往下乘也是负数)
当数组中有0的时候，则从0开始重新计算
该方法确实很巧妙
csharp
public class Solution{
public int MaxProduct(int[] nums){
int result = 1;
int max = int.MinValue;
//从左往右算
for(int i=0; i<nums.Length; i++){
result *= nums[i];
max = Math.Max(result,max);
if(nums[i] == 0){
result = 1;
}
}
//从右往左算
result = 1;
for(int i=nums.Length -1; i>=0; i--){
result *= nums[i];
max = Math.Max(result,max);
if(nums[i] == 0){
result = 1;
}
}
return max;
}
}