# [LeetCode 152] Maximum Product Subarray

### Question

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`.

### Analysis

This is a pretty difficult question. It’s hard to write bug-free solution if you have never practised before.

So the first idea that comes to me is the case of array element = 0. Why this case? cuz the maximum subarray MUST NOT CONTAIN 0 unless the input is like {-1, 0, -1}. So we could divide array from 0s and calculate max sum seperately. This idea is good, though a little difficult in coding. Read it here or here.

### Solution

After a bit exploration, I found a must easier apporach, thanks to code ganker and Yu. The idea is to simply ALWAYS CALCULATE preMax and preMin by using MAX/MIN(Val1, Val2, Val3) method.

### My Code

``````public class Solution {
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
} else if (A.length == 1) {
return A[0];
}

int preMax = A[0];
int preMin = A[0];
int max = A[0];

for (int i = 1; i < A.length; i++) {
int temp = preMin;
preMin = Math.min(Math.min(preMin * A[i], preMax * A[i]), A[i]);
preMax = Math.max(Math.max(temp * A[i], preMax * A[i]), A[i]);
max = Math.max(max, preMax);
}

return max;
}
}
``````