152. Maximum Product Subarray

leetcode網址

問題

找到一個subarry，且其所有數值的乘積是最大

Example 1:
Input: nums = [2,3,-2,4]
Output: 6
        [2,3] has the largest product 6.


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

Idea

用 Kadane's ALgorithm，用兩個loop，一個forward:前面到後面，一個backward:後面到前面，因為有負數所以可能有不同結果(ex. [-1, -1, -2])，最後的結果是這兩個loop的綜合評估

1. keep住一個 pro 來看累乘到目前的乘積
2. 如果 pro==0，就把他reset成1
3. 過程中不斷更新最大乘積

Solution

時間複雜度=O(N); 空間複雜度=O(1)

int maxProduct(vector<int>& nums) {
    int n=nums.size(), pro = 1, maxi=INT_MIN;
    for(int i=0; i<n; i++){
        pro*=nums[i];
        maxi = max(maxi, pro);
        if(pro==0)pro=1;        
    }
    
    pro=1;
    for(int i=n-1; i>=0; i--){
        pro*=nums[i];
        maxi = max(maxi, pro);
        if(pro==0)pro=1;        
    }
    
    
    return maxi;
}