# 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.

Example 1:

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

Example 2:

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

# Solution

Approach 1: DP.

# Code (Python)

Approach 1:

    def maxProduct(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        max_product = nums[0]
        min_product = nums[0]
        global_max = nums[0]
        for num in nums[1:]:
            temp = max_product * num
            max_product = max(temp, num, min_product * num)
            min_product = min(temp, num, min_product * num)
            global_max = max(global_max, max_product)
        
        return global_max

# Code (C++)

Approach 1:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int maxOfAll = nums[0];
        int prevMax = nums[0];
        int prevMin = nums[0];
        for (int i = 1; i < n; ++i)
        {
/*
            int wPrevMax = prevMax * nums[i];
            int wPrevMin = prevMin * nums[i];
            int currMax = std::max(std::max(wPrevMax, wPrevMin), nums[i]);
            int currMin = std::min(std::min(wPrevMax, wPrevMin), nums[i]);
*/
            int currMax;
            int currMin;
            if (nums[i] >= 0)
            {
                currMax = std::max(nums[i], nums[i] * prevMax);
                currMin = std::min(nums[i], nums[i] * prevMin);
            }
            else
            {
                currMax = std::max(nums[i], nums[i] * prevMin);
                currMin = std::min(nums[i], nums[i] * prevMax);
            }

            maxOfAll = std::max(maxOfAll, currMax);
            prevMax = currMax;
            prevMin = currMin;
        }
        return maxOfAll;
    }
};