# Maximum Product Subarray

## Question

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

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

**Tags**

LinkedIn Dynamic Programming Subarray

**Related Problems**

Medium Best Time to Buy and Sell Stock 41 %\
Medium Maximum Subarray Difference 23 %\
Easy Minimum Subarray 38 %\
Medium Maximum Subarray II

## Analysis

本题其实是Maximum Subarray Sum问题的延伸，不同的是这里需要考虑元素的符号。

DP的四要素

* **状态：**
  * `max_product[i]`: 以nums\[i]结尾的max subarray product
  * `min_product[i]`: 以nums\[i]结尾的min subarray product
* **方程：**
  * `max_product[i] = getMax(max_product[i-1] * nums[i], min_product[i-1] * nums[i], nums[i])`
  * `min_product[i] = getMin(max_product[i-1] * nums[i], min_product[i-1] * nums[i], nums[i])`
* **初始化：**
  * `max_product[0] = min_product[0] = nums[0]`
* **结果：**
  * 每次循环中 `max_product[i]` 的最大值

## Solution

**DP, with O(n) space, O(n) time**

```java
public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {

        int[] max = new int[nums.length]; // maximum product ending with nums[i]
        int[] min = new int[nums.length]; // minimum product ending with nums[i]

        max[0] = min[0] = nums[0];

        int result = max[0];

        for (int i = 1; i < nums.length; i++) {
            max[i] = min[i] = nums[i];
            if (nums[i] > 0) { // 区分nums[i]的符号
                max[i] = Math.max(max[i], nums[i] * max[i - 1]);
                min[i] = Math.min(min[i], nums[i] * min[i - 1]);
            } else {
                max[i] = Math.max(max[i], nums[i] * min[i - 1]);
                min[i] = Math.min(min[i], nums[i] * max[i - 1]);
            }
            result = Math.max(max[i], result);
        }

        return result;
    }
}
```

**DP - Simplified - O(n) space, O(1) time**

```java
class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] maxProduct = new int[n]; // max subarray product ending in nums[i]
        int[] minProduct = new int[n]; // min subarray product ending in nums[i]

        maxProduct[0] = nums[0];
        minProduct[0] = nums[0];
        int max = maxProduct[0];
        for (int i = 1; i < n; i++) {
            maxProduct[i] = Math.max(nums[i], Math.max(maxProduct[i - 1] * nums[i], minProduct[i - 1] * nums[i]));
            minProduct[i] = Math.min(nums[i], Math.min(maxProduct[i - 1] * nums[i], minProduct[i - 1] * nums[i]));
            max = Math.max(maxProduct[i], max);
        }
        return max;
    }
}
```

**DP, improved, with O(1) space, O(n) time**

```java
public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
        int result, currentMax, currentMin;
        result = currentMax = currentMin = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int temp = currentMax;
            currentMax = Math.max(nums[i], Math.max(currentMax * nums[i], currentMin * nums[i]));
            currentMin = Math.min(nums[i], Math.min(temp * nums[i], currentMin * nums[i]));

            result = Math.max(currentMax, result);
        }

        return result;
    }
}
```

O(1) space, O(n) time

```java
class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int maxPre = nums[0], minPre = nums[0], max = nums[0], maxHere, minHere;
        for (int i = 1; i < nums.length; i++){
            maxHere = Math.max(nums[i], Math.max(nums[i] * maxPre, nums[i] * minPre));
            minHere = Math.min(nums[i], Math.min(nums[i] * maxPre, nums[i] * minPre));
            max = Math.max(max, maxHere);
            maxPre = maxHere;
            minPre = minHere;
        }
        return max;
    }
}
```

Same idea but a more concise implementation

```java
int maxProduct(int A[], int n) {
    // store the result that is the max we have found so far
    int r = A[0];

    // imax/imin stores the max/min product of
    // subarray that ends with the current number A[i]
    for (int i = 1, imax = r, imin = r; i < n; i++) {
        // multiplied by a negative makes big number smaller, small number bigger
        // so we redefine the extremums by swapping them
        if (A[i] < 0)
            swap(imax, imin);

        // max/min product for the current number is either the current number itself
        // or the max/min by the previous number times the current one
        imax = max(A[i], imax * A[i]);
        imin = min(A[i], imin * A[i]);

        // the newly computed max value is a candidate for our global result
        r = max(r, imax);
    }
    return r;
}
```

## Reference

* [programcreek: Maximum Product Subarray](http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/)
* [Jiuzhang](http://www.jiuzhang.com/solutions/maximum-product-subarray/)
* [LeeCode Discussion](https://discuss.leetcode.com/topic/3607/sharing-my-solution-o-1-space-o-n-running-time/23)