［LeetCode］152. Maximum Product Subarray

This a task that asks u to compute the maximum product from a continue subarray. However, you need to watch

out the values' type contains positive, negative, zero.

I solved it using dynamic process in which there are two arrays to achieve the goal.

maxPro[i] : record the maximum product using nums[i] at end.

minPro[i] : record the minimum product using nums[i] at end.

Causing the neg and pos value types, we always can find the maximum product using the formula as below(maximum or minimum recording array):

　　maxPro[i] = max3(nums[i], nums[i] * maxPro[i - 1], nums[i] * minPro[i - 1]);
　　minPro[i] = min3(nums[i], nums[i] * maxPro[i - 1], nums[i] * minPro[i - 1]);

class Solution {
public:
    int max3(int a, int b, int c){
        return a > b? max(a, c): max(b, c);
    }
    
    int min3(int a, int b, int c){
        return a < b? min(a, c): min(b, c); 
    }
    
    int maxProduct(vector<int>& nums) {
        vector<int>maxPro(nums.size(), 0);
        vector<int>minPro(nums.size(), 0);
        int ans = nums[0];
        for(int i = 0; i < nums.size(); i ++){
            if(i == 0){
                maxPro[0] = nums[0];
                minPro[0] = nums[0];
            }else{
                maxPro[i] = max3(nums[i], nums[i] * maxPro[i - 1], nums[i] * minPro[i - 1]);
                minPro[i] = min3(nums[i], nums[i] * maxPro[i - 1], nums[i] * minPro[i - 1]);
            }
            if(ans < maxPro[i]) ans = maxPro[i];
        }
        return ans;
    }
};

［LeetCode］152. Maximum Product Subarray

推荐阅读