本文主要是介绍leetcode题：72. 152. 乘积最大子序列（中等），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述：152. 乘积最大子序列（中等）
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题思路
1、由于是乘积，所以当遇到0的时候乘积会为了0.所以数组由n个0元素分割成n+1个子数组。分别统计n+1个子数组的最大连续子序列。
2、定义count_now 保存从第一个数字（被分割后的子数组）到当前数字的乘积，count_all保存所有子数组的最大子数组。left指针，right指针分别指向第一和最后一个负数。
当count_all > 0的时候当前不包含0的子数组的最大子数组乘积就是count_now。
当count_all < 0 说明子数组有负数
1)当left == right（只有一个负数），则计算left和right左右两边的乘积和，取最大值，为count_now。
2)当left < right 则计算right左右一个元素的乘积，和left开始到子数组末尾的的乘积，取最大值为count_now。
然后更新count_all为所有count_now的最大值
3、另外要注意边界条件，当总数组不存在0并且最大乘积为负数的时候，count_all也为负数，但是总数组存在0并且最大乘积为负数的时候count_all 等于0。
三、代码
class Solution {
public:int maxProduct(vector<int>& nums) {int mut = 1;int max_sum = INT_MIN;vector<int> dp(nums.size(),0);int left = -1;int right = -1;int max_tmp = INT_MIN;bool is_zero = false;int count = 0;for(int i = 0;i<=nums.size();i++){if( i== nums.size()|| nums[i] == 0){if(i == 0)continue;if(dp[i-1] >= 0){max_sum = max(dp[i-1],max_sum);left = -1;right = -1;}else if(left >= 0 && left == right){max_tmp = dp[i-1];if(count > 1){if(left > 0)max_tmp = max(dp[left-1],dp[i-1]/dp[left]);elsemax_tmp = dp[i-1]/dp[left];}max_sum = max(max_tmp,max_sum);//cout<<"sum="<<max_sum<<endl;}else if(left == -1){max_sum = max(dp[i-1],max_sum);}else if(left >= 0 && left != right){max_tmp = max(dp[right-1],dp[i-1]/dp[left]);max_sum = max(max_tmp,max_sum);}left = -1;right = -1;count = 0;if(i == nums.size())break;dp[i] = nums[i];is_zero = true;continue;}count++;if(i == 0){dp[i] = nums[i];if(nums[i] < 0){left = i;right = i;}}else{if(nums[i] == 0 ){dp[i] = nums[i];continue;} else if(dp[i-1] == 0){dp[i] = nums[i];}else{dp[i] = dp[i-1] * nums[i];}}if(nums[i] < 0){if(left == -1 && right == -1 ){left = i;right = i;}else{right = i;}}}// print(dp);if(max_sum < 0 && is_zero == true)max_sum = 0;return max_sum;}void print(vector<int> & dp){for(int i = 0; i< dp.size();i++){cout<<dp[i]<<endl;}}
};
这篇关于leetcode题：72. 152. 乘积最大子序列（中等）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
