###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++` `Top 100 Liked Questions`

# 152. Maximum Product Subarray

## [題目連結:] https://leetcode.com/problems/maximum-product-subarray/description/

## 題目:
Given an integer array ```nums```, find a contiguous non-empty subarray within the array 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.

A **subarray** is a contiguous subsequence of the array.

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

## 解題想法:

* 此題為求連續數組最大的乘積
* 對於**最大乘積**需考慮:
* 正正相乘
* 負負相乘
* 設三變量:
* ans = nums[0]
* cur_min=nums[0] 紀錄連續最小乘積
* cur_max=nums[0] 紀錄連續最大乘積
* for i in range(1,len(nums)):
* 對於當前的num[i]值: **若為負**
* 須將cur_min、cur_max交換
* 給最小值一個有機會負負得正翻身的機會
* 對於每次cur_min、cur_max更新:
* **是要跟當前nums[i]比較大小**:
* 因為採連續機制
* cur_min = min(cur_min*nums[i] , **nums[i]** )
* 以cur_min 為例:
* 若選nums[i]:
* 表示以現在nums[i]為基準從新累計
* 若選cur_min*nums[i]:
* 表示繼續累計
* cur_max = max(cur_max*nums[i] , **nums[i]**)
* 最終ans只需與cur_max進行比較更新大的即可

* 相關基礎題 : [53. Maximum Subarray](/J6Id4JL3Qz-glozT2R9bDw)
* 皆為time O(n) space O(1)

## Python:

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        cur_min=nums[0]
        cur_max=nums[0]
        for i in range(1,len(nums)):
            #若當前的值為負:
            #將low與high調換: 給low一個翻身的機會
            if nums[i]<0:
                cur_min,cur_max=cur_max,cur_min
            cur_min = min(cur_min*nums[i],nums[i])
            cur_max = max(cur_max*nums[i],nums[i])
            res = max(res,cur_max)
        return res
    

result = Solution()
nums = [2,3,-2,4]
ans = result.maxProduct(nums)
print("P152:",ans)

## C++:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res=nums[0], curMin=nums[0], curMax=nums[0];
        for (int i=1; i<nums.size(); i++){
            if (nums[i]<0) //#include <algorithm>
                swap(curMax,curMin);
            curMin=min(curMin*nums[i],nums[i]);
            curMax=max(curMax*nums[i],nums[i]);
            res=max(res,curMax);
        }
        return res;
    }
};

int main(){
    vector<int> nums={2,3,-2,4};
    Solution res;
    int ans=res.maxProduct(nums);
    cout<<ans<<endl;
    return 0;
}