# Leetcode 152. Maximum Product Subarray
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/maximum-product-subarray/ 。

想法 :

1. 如果有單數個負數，移除最小的負並把數全部乘起來。
### 這裡我們把它寫成雙向，也就是看成只有一個負數，並比較這個負數的左右兩側相乘結果。

2. 如果有複數個負數，直接乘起來。
3. 如果有0，就要以0為分割，切成左右半獨立計算答案，並考慮0是否可能為答案。
### 這裡我們使用Kadane's Algorithm，也就是如果遇到0就把現在的乘積變1。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int l = nums.size(), ans = -20,pro = 1;
        
        for(int i=0 ; i<l ; i++){
            pro *= nums[i];
            ans = max(ans , pro);
            if(pro == 0) pro = 1;
        }
        
        pro=1;
        for(int i=l-1 ; i>=0 ; i--){
            pro *= nums[i];
            ans = max(ans , pro);
            if(pro == 0) pro = 1;
        }
        
        return ans;
    }
};