## 152. Maximum Product Subarray

###### tags: `Dynamic Programming` `Medium`

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

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

:::

<hr/>

### Sol
:::spoiler Code

:::

<hr/>

### 東

:::spoiler Code

:::

<hr/>

### Jessie

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

:::

<hr/>

### Haoyu

:::spoiler Code
#### Try 1: Fail, test case = [-2, 3, -4]

var maxProduct = function(nums) {
    const maxSubarrayProducts = [nums[0]];
    const resSubarrayProducts = [nums[0]];

    for (let i = 1; i < nums.length; i += 1) {
        maxSubarrayProducts[i] = Math.max(maxSubarrayProducts[i - 1] * nums[i], nums[i]);
        resSubarrayProducts[i] = Math.max(resSubarrayProducts[i - 1], maxSubarrayProducts[i]);
    }

    return resSubarrayProducts[nums.length - 1];
};

#### Try 2: https://www.youtube.com/watch?v=0Kpz-ChuQIE

var maxProduct = function(nums) {
    const maxSubarrayProducts = [nums[0]];
    const minSubarrayProducts = [nums[0]];
    const resSubarrayProducts = [nums[0]];

    for (let i = 1; i < nums.length; i += 1) {
        maxSubarrayProducts[i] = Math.max(Math.max(maxSubarrayProducts[i - 1] * nums[i], minSubarrayProducts[i - 1] * nums[i]), nums[i]);
        minSubarrayProducts[i] = Math.min(Math.min(minSubarrayProducts[i - 1] * nums[i], maxSubarrayProducts[i - 1] * nums[i]), nums[i]);
        resSubarrayProducts[i] = Math.max(resSubarrayProducts[i - 1], maxSubarrayProducts[i]);
    }

    return resSubarrayProducts[nums.length - 1];
};

#### Try 3: Optimize space complexity

var maxProduct = function(nums) {
    let max = nums[0];
    let min = nums[0];
    let res = nums[0];

    for (let i = 1; i < nums.length; i += 1) {
        const temp = max;

        max = Math.max(Math.max(temp * nums[i], min * nums[i]), nums[i]);
        min = Math.min(Math.min(min * nums[i], temp * nums[i]), nums[i]);
        res = Math.max(res, max);
    }

    return res;
};

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::