> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/dynamic-programming/152.-maximum-product-subarray.md).

# 152. Maximum Product Subarray

[Given an integer array `nums`, find the contiguous subarray within an array (containing at least one number) which has the largest product.](https://leetcode.com/problems/maximum-product-subarray/)

{% hint style="info" %}
dynamic programming, use a int to keep track of minimal product of subarrays

```java
dp[i+1] = Math.max(nums[i+1], dp[i]*nums[i+1], preMin*nums[i+1]);
```

{% endhint %}

```java
class Solution {
    public int maxProduct(int[] nums) {
        // let dp[i] be the largest product of subarray end at index of i
        // let preMin be the smallest product of subarray end at index of i
        // dp[i+1] = Math.max(nums[i+1], dp[i]*nums[i+1], preMin*nums[i+1]);
        
        // use int to record min prodction
        int preMin = nums[0];
        // use nums[] to record max production
        
        int res = nums[0];
        for (int i=1; i<nums.length; i++){
            int min = Math.min(preMin*nums[i], nums[i-1]*nums[i]);        
            int max = Math.max(preMin*nums[i], nums[i-1]*nums[i]);
            preMin = Math.min(nums[i], min);
            
            nums[i] = Math.max(nums[i], max);                        
            res = nums[i]>res ? nums[i] : res;
            
        }
        return res;
    }
}
```