# 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;
}

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;
int max = nums;

int production = nums;
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.
}
``````