152. Maximum Product Subarray
1. Description
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
2. Example
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.
3. Solutions
Queue
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
dpmax[i] means the max product ends at the index i, dpmin[i] means the min product(we hope it is negative) ends at the index i
dpmax[i] = max(dpmax[i-1] * i_nums[i], max(i_nums[i], dpmin[i-1] * i_nums[i]))
dpmin[i] = min(dpmin[i-1] * i_nums[i], min(i_nums[i], dpmax[i-1] * i_nums[i]))
dp[i] = max(dp[i-1], dpmax[i])
// we hope dpmin[i] is a very small negative number, so abs(dpmin[i]) is very big
// then, the next time we meet a negative number, we could make their product very big
// and also, we could remove its negative sign, and get a big result
class Solution {
public:
// int maxProduct(vector<int>& nums)
int maxProduct(const vector<int> &i_nums)
{
if(i_nums.empty()) return 0;
int result = i_nums.front(), maxSubProduct = i_nums.front(), minSubProduct = i_nums.front();
for (int i = 1; i < i_nums.size(); ++i)
{
int previousMaxProduct = maxSubProduct, previousMinProduct = minSubProduct;
maxSubProduct = max(previousMaxProduct * i_nums[i], max(i_nums[i], previousMinProduct * i_nums[i]));
minSubProduct = min(previousMinProduct * i_nums[i], min(i_nums[i], previousMaxProduct * i_nums[i]));
result = max(maxSubProduct, result);
}
return result;
}
};