# C++ 4 ms solution with explaination

• ``````int maxProduct(vector<int>& nums) {
if (0 == nums.size()) return 0;
if (1 == nums.size()) return nums[0];
//
// Take an example as below:
// ... 0, 2, -6, ... , -5, 3, 0, ...
// If the count of negative numbers between two zeros are even, using all.
// If the count of negative numbers between two zeros are odd:
//   Get rid of one side as below: 'current prod/-12'
//     (2 * -6) == -12 and (-5 * 3) == -15
//
int max = INT_MIN;
int begin = 0, prod = INT_MIN;
for (int i = 0, size=nums.size(); i < size; ++i) {
if (0 == nums[i]) {
// begin <-> end
prod = extractMaxProd(nums, begin, i-1, prod);
if (prod > max) { max = prod; }
if (0    > max) { max = 0; } // Include 0

while (++i < size && 0 == nums[i]) { }

prod  = INT_MIN;
begin = i;

--i; // There is an extra ++ at end of 'for'
} else {
if (INT_MIN == prod) { prod = nums[i]; } // First one.
else { prod *= nums[i]; }
}
}

prod = extractMaxProd(nums, begin, nums.size()-1, prod);
if (prod > max) { max = prod; }

return max;
}

inline int extractMaxProd(vector<int>& nums, int begin, int end, int prod) {
if (begin == end || prod > 0) return prod;

// Handle 'prod < 0' situation
int leftProd = 1;
for (int j=begin; j<=end; ++j) {
leftProd *= nums[j];
if (leftProd < 0) break;
}
int rightProd = 1;
for (int j=end; j>=begin; --j) {
rightProd *= nums[j];
if (rightProd < 0) break;
}
prod /= (leftProd > rightProd) ? leftProd : rightProd;
return prod;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.