Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.Example 2:
Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.===========================================================================
这个题与最大连续和比较相似，不过这个是最大乘积子序列，所以，如果最后得到负数的话，不能舍弃掉，因为这个负数乘上接下来的数，也有可能得到最大正数。
所以，这次要建立两个变量，分别记录最小乘积和最大乘积。
C++代码：
class Solution { public: int maxProduct(vector<int>& nums) { if(nums.size() == 0)return 0; if(nums.size() == 1)return nums[0]; int n = nums.size(); int negative = 1,positive = 1; vector<int> dp(n,1); int res = -0x3f3f3f3f; for(int num : nums){ positive *= num; negative *= num; if(positive < negative){ swap(positive,negative); } positive = max(positive,num); negative = min(negative,num); res = max(positive,res); } return res; } };
转载于:https://www.cnblogs.com/Weixu-Liu/p/10846202.html
