乘积最大子数组（数组篇）
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例1：
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例2：
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
示例3：
输入: [3,-1,4]
输出: 4
解法1：
思路：遍历数组时，计算当前最大值，并不断更新。
令imax为当前最大值，有imax=max(imax*nums[i],nums[i])由于存在负数，会导致最大值变成最小值，所以还需要维护当前最小值imin
当负数出现时，交换 imax 和 imin 。
首先假设存在某个最大乘积，然后对数组遍历，在经过每个元素的时候，有以下四种情况：
如果该元素为正数：
如果到上一个元素为止的最大乘积也是正数，那么直接乘上就好了，同样的最大乘积也会变得更大
如果到上一个元素为止的最大乘积是负数，那么最大乘积就会变成该元素本身，且连续性被断掉
如果该元素为负数：
如果到上一个元素为止的最大乘积也是负数，那么直接乘上就好了，同样的最大乘积也会变得更大
如果到上一个元素为止的最大乘积是正数，那么最大乘积就会不变，且连续性被断掉
以上四种情况中说到的最大乘积都是临时最大乘积，每遍历新的元素都需要进行比较来确定真正的最大乘积。
class Solution {public:int maxProduct(vector<int>& nums) {int len=nums.size();//一个保存最大值，一个保存最小值int imax=1,imin=1,res=INT_MIN;for(int i=0;i<len;i++){//若数组的数是负数，会导致最大值变成最小值，最小值变成最大值，因此交换if(nums[i]<0){int tmp=imax;imax=imin;imin=tmp;}imax=max(imax*nums[i],nums[i]);imin=min(imin*nums[i],nums[i]);res=max(imax,res);}return res;}};
解法2：
思路：求最大值，可以看成求被0拆分的各个子数组的最大值
当数组中不存在0时，分两种情况：
一是，负数个数为奇数个，从左边开始 乘到最后一个负数停止有一个最大值，从右边开始称也有一个最大值 ，两者取大。
二是，负数个数为偶数个，结果为数组所有元素的乘积。
class Solution {public:int maxProduct(vector<int>& nums) {int len=nums.size();int res=INT_MIN,multy=1;for(int i=0;i<len;i++){multy*=nums[i];if(res<multy)res=multy;if(nums[i]==0)multy=1;}multy=1;for(int i=len-1;i>=0;i--){multy*=nums[i];if(res<multy)res=multy;if(nums[i]==0)multy=1;}return res;}};