Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within the array that has the largest product.
Constraints:
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Examples:
Input: [2,3,-2,4]
Output: 6
Explanation: The subarray [2,3] has the largest product 6.
Input: [-2,0,-1]
Output: 0
Explanation: The subarray [0] has the largest product 0.
Solutions
Dynamic Programming
We use two variables max and min to keep track of the maximum and minimum product ending at the current position. If the current number is negative, we swap max and min because a negative number can turn a maximum product into a minimum product and vice versa. Then we update max and min by taking the maximum and minimum of the current number and the product of the current number and the previous max and min. Finally, we update the result by taking the maximum of the current result and max.
int maxProduct(vector<int>& nums) {
int max_val = nums[0], min_val = nums[0], result = nums[0];
for (int i = 1;
i < nums.size();
i++) {
if (nums[i] < 0) swap(max_val, min_val);
max_val = max(nums[i], max_val * nums[i]);
min_val = min(nums[i], min_val * nums[i]);
result = max(result, max_val);
}
return result;
}Follow-up:
What if the input array is empty?
