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

Given an integer array `nums`, find a subarray that has the largest product, and return _the product_.

The test cases are generated so that the answer will fit in a **32-bit** integer.

**Example 1:**

**Input:** nums = \[2,3,-2,4\]
**Output:** 6
**Explanation:** \[2,3\] has the largest product 6.

**Example 2:**

**Input:** nums = \[-2,0,-1\]
**Output:** 0
**Explanation:** The result cannot be 2, because \[-2,-1\] is not a subarray.

**Constraints:**

- `1 <= nums.length <= 2 * 104`
- `-10 <= nums[i] <= 10`
- The product of any prefix or suffix of `nums` is **guaranteed** to fit in a **32-bit** integer.

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        // 用一個變數 curMax 存目前為止最大的乘積
        int curMax = nums[0];
        
        // 用一個變數 curMin 存目前為止最大的乘積
        int curMin = nums[0];
        int res = curMax;

        for (int i = 1; i < n; i++) {
            int cur = nums[i];
            // 有三種組合，求最大值
            int temp_max = max({cur, curMax * cur, curMin * cur});
            
            // 有三種組合，求最小值
            curMin = min({cur, curMax * cur, curMin * cur});
            
            // temp_max 的作用是讓 curMax 暫存先前的值
            curMax = temp_max;

            res = max(curMax, res);
        }
        return res;        
    }
};

:::success
- 時間複雜度：$O(N)$
- 空間複雜度：$O(1)$
:::