152. 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;        
    }
};

• 時間複雜度：
  $O(N)$
• 空間複雜度：
  $O(1)$