152. Maximum Product Subarray (Medium)
https://leetcode.com/problems/maximum-product-subarray/
Given an integer array nums
, find the contiguous subarray within an array (containing at least one number) which has the largest product.
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.
Solutions
class Solution {
public int maxProduct(int[] nums) {
int ans = 0;
if (nums == null || nums.length == 0) {
return ans;
}
// [-2]
if (nums.length == 1) {
return nums[0];
}
int min = 0;
int max = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
// max could be 0, so choose the larger outcome
max = Math.max(max * nums[i], nums[i]);
// min <= 0, so min * nums[i] will be much smaller
min = min * nums[i];
}
if (nums[i] == 0) {
// start a new searching process and break up with previous consecutive sub array.
max = 0;
min = 0;
}
if (nums[i] < 0) {
int tmp = max;
// since nums[i]<0, you can only execute min * nums[i] to get a value >= 0 if you want to cover nums[i]
max = min * nums[i];
// since nums[i]<0, you can only execute previous_max * nums[i] to get a value >= 0 if you want to cover nums[i]
min = Math.min(nums[i], tmp * nums[i]);
}
ans = Math.max(ans, max);
}
return ans;
}
}
Incorrect Solutions
1.
class Solution {
// Incorrect solution, fail to pass case [3, -1, 4]
// The key idea of this solution is to keep the min when calculate the production. We need to keep
// the min, if it's a negative value and can be a large positive if multiplied by negative value.
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int production = 1;
for (int i = 0; i < nums.length; i++) {
production *= nums[i];
max = Math.max(max, production);
min = Math.min(min, production);
// If you meets zero, you need to start over the production calculation.
if (nums[i] == 0) {
production = 1;
}
}
return max;
}
}
2.
class Solution {
// Incorrect solution, fail to pass case [0,2], [3, -1, 4]
// The key idea of this solution is to keep the min when calculate the production. We need to keep
// the min, if it's a negative value and can be a large positive if multiplied by negative value.
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int min = nums[0];
int max = nums[0];
int production = nums[0];
for (int i = 1; i < nums.length; i++) {
production *= nums[i];
max = Math.max(max, production);
min = Math.min(min, production);
// If you meets zero, you need to start over the production calculation.
if (nums[i] == 0) {
production = 1;
}
}
return max;
}
}
3.
class Solution {
// Following idea is trivial and complicated.
// This problem is not that complicated and at the first glance you may have some ideas.
// FIXME Right blow statement is incorrect.
// The continuous sub array must contain as many positive values as possible. Any sub arrays
// incorporate 0 or negative values will result in a negative production.
// The truth is that the production can be positive if the sub array doesn't contain 0 and
// consists of even count of negative values.
// There are two situations we will stop to check the previous scanned sub array.
// 1. Hit 0, since 0 times everything will be 0
// 2. Reach the end of the array.
// Above both situation we need to sort out the impact of the negative values in the previous sub array.
// All the negative values are expected to be processed respectively. It is recommended to use a Map to
// keep the appeared negative values and corresponding productions.
}