[LeetCode]Maximum Product Subarray

和max subarray的解法很类似，区别在这里负负可以得正，所以我们除了要记录局部最大值外还要记录局部最小值。首先我们定义几个变量，localMax[i]为以i结尾的subarray中最大的值，localMin[i]为以i结尾的subarray中最小的值；globalMax[i]定义为[0, i]范围中最大的subarray，globalMin[i]定义为[0, i]范围中最小的subarray，递推公式如下：

• if A[i] >= 0
• localMax[i] = max(localMax[i - 1] * A[i], A[i]);
• localMin[i] = min(localMin[i - 1] * A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);
• if A[i] < 0
• localMax[i] = max(localMin[i - 1] * A[i], A[i]);
• localMin[i] = min(localMax[i - 1] * A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);

可以开两个array来记录，不过可以优化到常数空间时间复杂度，时间复杂度O(n)，代码如下：

	class Solution {
	public:
	int maxProduct(vector<int>& nums) {
	int len = nums.size();
	if(!len)return 0;
	int maxP = nums[0], minP = nums[0], res = nums[0];
	for(int i = 1; i < nums.size(); ++i)
	{
	int num = nums[i];
	if(num >= 0)
	{
	maxP = max(num, num * maxP);
	minP = min(num, num * minP);
	}
	else
	{
	int copyMax = maxP, copyMin = minP;
	maxP = max(num, num * copyMin);
	minP = min(num, num * copyMax);
	}
	res = max(res, maxP);
	}
	return res;
	}
	};

view raw Maximum Product Subarray.cpp hosted with ❤ by GitHub