> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/maximum-product-subarray.md).

# 152. Maximum Product Subarray

### Description

Given an integer array `nums`, find the contiguous subarray within an array (containing at least one number) which has the largest product.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/maximum-product-subarray/)
* [Leetcode](https://leetcode.com/problems/maximum-product-subarray/)
* [ProgramCreek](https://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[2, 3, -2, 4]

**Output:** 6

**Explanation:** \[2, 3] has the largest product 6.
{% endtab %}

{% tab title="Example 2" %}
**Input:** \[-2, 0, -1]

**Output:** 0

**Explanation:** The result cannot be 2, because \[-2, -1] is not a subarray.
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N^2) where N is the size of nums. Since we are 
 *    checking every possible contiguous subarray following every element 
 *    in nums we have quadratic runtime.
 * Space complexity : O(1) since we are not consuming additional space other 
 *    than two variables: result to hold the final result and accu to 
 *    accumulate product of preceding contiguous subarrays.
 */

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;

        int result = nums[0];

        for (int i = 0; i < nums.length; i++) {
            int accu = 1;
            for (int j = i; j < nums.length; j++) {
                accu *= nums[j];
                result = Math.max(result, accu);
            }
        }

        return result;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public int maxProduct(int[] nums) {
        int res = nums[0], min = nums[0], max = nums[0];
        for(int i = 1; i < nums.length; i++) {
            int tmp = max;
            int n = nums[i];
            
            max = Math.max(Math.max(n, max*n), min*n);
            min = Math.min(Math.min(n, min*n), tmp*n);
            
            if(max > res) res = max;
        }
        return res;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*