## Maximum Product Subarray Problem

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.

## Reduction Transition Function

Product subarray is different from sum subarray in that:

- A negative number * a negative number produce a big positive number
- A negative number * a positive number produce a small negative number
- Thus to get the localMax[i + 1], we may need to know the localMin[i]
- So we want to record the locaMax and localMin at each step.

Thus we have the following RTF:

- if nums[i + 1] >= 0:
- localMax[i + 1] = Math.max(localMax[i] * nums[i + 1], nums[i]);
- localMin[i + 1] = Math.min(localMin[i] * nums[i + 1], nums[i]);

- if nums[i + 1] < 0:
- localMax[i + 1] = Math.max(localMin[i] * nums[i + 1], nums[i]);
- localMin[i + 1] = Math.min(localMax[i] * nums[i + 1], nums[i]);

The following diagram illustrates the algorithm:

## Implementation

The following is the implementation of the algorithm:

```
public int maxProduct(int[] nums) {
int localMax = nums[0];
int localMin = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] >= 0) {
localMax = Math.max(nums[i], nums[i] * localMax);
localMin = Math.min(nums[i], nums[i] * localMin);
} else if (nums[i] < 0) {
int localMaxTemp = Math.max(nums[i], nums[i] * localMin);
localMin = Math.min(nums[i], nums[i] * localMax);
localMax = localMaxTemp;
}
max = Math.max(localMax, max);
}
return max;
}
```

- Runtime: O(n)