# 152     Maximum Product Subarray

## 152. [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/description/)

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

## 2. Implementation

**(1) DP**

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

        int n = nums.length;
        int res = nums[0];
        int max = nums[0];
        int min = nums[0];

        for (int i = 1; i < n; i++) {
            if (nums[i] >= 0) {
                max = Math.max(nums[i], max * nums[i]);
                min = Math.min(nums[i], min * nums[i]);
            }
            else {
                int temp = max;
                max = Math.max(nums[i], min * nums[i]);
                min = Math.min(nums[i], temp * nums[i]);
            }
            res = Math.max(res, max);
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n), 空间复杂度O(1)