[LeetCode] 152. Maximum Product Subarray

轉自LeetCode

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

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

<Solution>
這題是要找出有最大乘積的 subarray，回傳的答案回傳乘積就好

解題時要注意，會有 0 和負數的情況，想法如下

• prvMax 是指上一輪最大的乘積，如果沒有比 1 大，就設為 1

• 當數值大於零的時候，就是相乘

• 當數值小於等於零的時候，curMax = curMin * n，curMin = prvMax * n

• 每一次 iteration 結束，紀錄最大的乘積是多少

code 如下

	class Solution {
	public:
	int maxProduct(vector<int>& nums) {
	if(nums.empty()) {
	return 0;
	}
	int ans = nums[0];
	int curMax = 1, curMin = 1;
	int prvMax;
	for(const auto &n : nums) {
	prvMax = max(curMax, 1);
	if(n > 0) {
	curMax = prvMax * n;
	curMin *= n;
	}
	else {
	curMax = curMin * n;
	curMin = prvMax * n;
	}
	ans = max(ans, curMax);
	}
	return ans;
	}
	};

view raw maxProductSubarray_1.cpp hosted with ❤ by GitHub

相同思路，但不同的寫法

• 正數，直接相乘

• 負數，那麼原本最小的會變最大，最大變最小

• 遇到 0，保持之前的最大和最小

綜合上面，可以導出

max product = max( current max, current num, current min)
min product = min( current max, current num, current min)

code 如下(參考資料)

	class Solution {
	public:
	int maxProduct(vector<int>& nums) {
	if(nums.empty()) {
	return 0;
	}
	int ans = nums[0], maxP = nums[0], minP = nums[0];
	int newMax, newMin;
	for(int i = 1; i < nums.size(); i++) {
	newMax = maxP * nums[i];
	newMin = minP * nums[i];
	//>> find local max and min
	maxP = max(max(nums[i], newMax), newMin);
	minP = min(min(nums[i], newMax), newMin);
	ans = max(ans, maxP);
	}
	return ans;
	}
	};

view raw maxProductSubarray_2.cpp hosted with ❤ by GitHub