LeetCode 152.Maximum Product Subarray

LeetCode 152.Maximum Product Subarray

Description:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example:

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

---

分析：

需要保存临时最大值和最小值，因为最大值乘以一个正数可能构成新的最大值，而最小值乘以负数也可能构成新的最大值。
result是要求的结果，maxValue为nums[i]之前的，和nums[i]相邻的乘积的最大值，minValue为nums[i]之前的，和nums[i]相邻的乘积的最小值。
首先令result、maxValue和minValue都为nums[0], i从nums[1]开始一直到结束，tempMax为考虑是否选择之前的maxValue与nums[i]相乘，如果相乘结果更大就保留，否则就选择nums[i]本身为最大。tempMin同理～
然后maxValue和minValue比较tempMax/tempMin与minValue * nums[i]的大小关系，maxValue取较大值，minValue取较小值～
而result是取所有maxValue中的最大值～最后返回result～

---

代码如下：

解法一：

class Solution {
public:
	int maxProduct(vector<int>& nums) {
		int size = nums.size();
		if (size == 0) return 0;
		int result = nums[0], maxValue = nums[0], minValue = nums[0];
		for (int i = 1; i < nums.size(); i++) {
			int tempMax = max(nums[i], maxValue * nums[i]);// 最大值乘以一个数可能成为新的最大值
			int tempMin = min(nums[i], maxValue * nums[i]);// 最大值乘以一个负数可能成为最小值
			maxValue = max(tempMax, minValue * nums[i]);// 最小值乘以一个负数可能成为最大值
			minValue = min(tempMin, minValue * nums[i]);// 最小值乘以一个数可能成为新的最小值
			result = max(maxValue, result);
		}
		return result;
	}
};

解法二：

class Solution {
public:
	int maxProduct(vector<int>& nums) {
		int size = nums.size();
		int frontProduct = 1, backProduct = 1;
		int result = INT_MIN;
		for (int i = 0; i < size; i++) {
			frontProduct *= nums[i];
			backProduct *= nums[size - i - 1];
			result = max(result, max(frontProduct, backProduct));
			frontProduct = frontProduct == 0 ? 1 : frontProduct;
			backProduct = backProduct == 0 ? 1 : backProduct;
		}
		return result;
	}
};