［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(), );

        vector<int>minPro(nums.size(), );

        int ans = nums[];

        for(int i = ; i < nums.size(); i ++){

            if(i == ){

                maxPro[] = nums[];

                minPro[] = nums[];

            }else{

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

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

            }

            if(ans < maxPro[i]) ans = maxPro[i];

        }

        return ans;

    }

};

巴特西

［LeetCode］152. Maximum Product Subarray

最新文章

热门文章