LeetCode刷题的一天（5）

很遗憾，今天就写了一道题。

今天有点忙，也有点飘、
早上整理完MySQL的收藏夹，接了个专访。

下午午睡了一下发现起晚了，主要是整个人就昏昏沉沉的。再优化了一下专访内容，就开始刷题了。

中等题·乘积最大的数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

  

 

  
1
  
2
  
3
 

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

  

 

  
1
  
2
  
3
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

最开始的思路是这样的（忽略了0）：将两两负数视为正数，就会导致要么结果是正数，要么是负数。如果是负数，就把结果从头除到它正数为止，在拿原结果从尾巴向前除到它为正数为止。然后比对。

但是，提交之后发现我把0给忘了。凉凉，直接白给。

于是调整战略，以0为分界区，对这个数组分成一块一块儿的（原地），然后对每一块儿使用上面的办法，并且纪录每一块儿的最大值，然后进行比对。方法是可以解决问题，就是太繁琐，费时间。

然后参考了一下题解，看了半天没看明白，讲的稀里糊涂的（像我这种智商的，就跟我讲白话吧），看了半天。

后来，看另一个人的题解，虽然他是错的，验证出来他就是错的，但是他有句话说的好，我看明白了：遇到负数的时候，会把最大的变成最小的，会把最小的变成最大的。

所以，我们在向前推进的时候，只要纪录下当前最大和当前最小即可。
为什么要记下当前最大？因为会碰到0啊，0啊！！！

那什么是当前最大？就是前一个最大的数×当前数组的数（可能是正数，也可能是0，也可能是负数），与当前数组的数当中比较大的那个。
那什么是当前最小？上面比较小的那个。

代码实现

int maxProduct(vector<int>& nums) { vector <int> maxF(nums), minF(nums); for (int i = 1; i < nums.size(); ++i) { maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i])); //其实这里的两个max，只是因为一个max只能放两个参数，没别的意思。 minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i])); } return *max_element(maxF.begin(), maxF.end());
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

再优化一下：

int maxProduct(vector<int>& nums) { int maxF = nums[0], minF = nums[0], ret = nums[0]; for (int i = 1; i < nums.size(); ++i) { int imax = maxF, imin = minF; maxF = max(imax * nums[i], max(nums[i], imin * nums[i])); minF = min(imin * nums[i], min(nums[i], imax * nums[i])); ret = max(maxF, ret); } return ret;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

这样还可以省掉一轮的遍历。

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/114648895