Maximum Product Subarray

LeetCode #152

Description:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example:

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Idea:

Code:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty()) return 0;

        int min_sofar=nums[0];
        int max_sofar=nums[0];
        int max_all=nums[0];

        for(int i=1; i<nums.size(); ++i){
            int max_tmp=threeMax(min_sofar*nums[i], nums[i], max_sofar*nums[i]);
            int min_tmp=threeMin(min_sofar*nums[i], nums[i], max_sofar*nums[i]);
            max_sofar=max_tmp;
            min_sofar=min_tmp;
            // cout<<max_sofar<<' '<<min_sofar<<endl;
            max_all=max(max_all, max_sofar);
        }

        return max_all;

    }

    int threeMax(int i, int j, int k){
        return max(max(i, j), k);
    }
    int threeMin(int i, int j, int k){
        return min(min(i, j), k);
    }
};