152. Maximum Product Subarray

/*
 * @lc app=leetcode id=152 lang=cpp
 *
 * [152] Maximum Product Subarray
 *
 * https://leetcode.com/problems/maximum-product-subarray/description/
 *
 * algorithms
 * Medium (34.13%)
 * Likes:    19009
 * Dislikes: 763
 * Total Accepted:    1.5M
 * Total Submissions: 4.3M
 * Testcase Example:  '[2,3,-2,4]'
 *
 * 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 * 10^4
 * -10 <= nums[i] <= 10
 * The product of any subarray of nums is guaranteed to fit in a 32-bit
 * integer.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();

        int curMax = nums[0], curMin = nums[0];
        int res = curMax;

        for (int i = 1; i < n; i++)
        {
            int cur = nums[i];
            int tempMax = max({cur, curMax * cur, curMin * cur});

            curMin = min({cur, curMax * cur, curMin * cur});
            curMax = tempMax;
            res = max(curMax, res);
        }
        return res;
    }
};
// @lc code=end

• T: $O(N)$
• S: $O(1)$