152. Maximum Product Subarray

Description:

https://leetcode.com/problems/maximum-product-subarray/#/description

Algorithm:

This is subarray question again.

Should record maxProduct and minProduct

minProduct = min(min(temp_min * nums[i], temp_max * nums[i]), nums[i]);
maxProduct = max(max(temp_min * nums[i], temp_max * nums[i]), nums[i]);

Code:

class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
int result = nums[0];
int minProduct = nums[0];
int maxProduct = nums[0];
for (int i = 1; i < n;i++)
{
int temp_max = maxProduct;
int temp_min = minProduct;
minProduct = min(min(temp_min * nums[i], temp_max * nums[i]), nums[i]);
maxProduct = max(max(temp_min * nums[i], temp_max * nums[i]), nums[i]);
result = max(result, maxProduct);
}
return result;
}
};

Timing & Space:

O(n) & O(1)