Two clean different solutions C++, well-commented


  • 3
    class Solution {
    public:
        //min can turn max when encountering another negative number
        //so we have to record all the min and max values;
    	int maxProduct(vector<int>& nums) 
        {
            int size = nums.size(), maxProduct = nums[0];
            int maxProducts[size]{0}, minProducts[size]{0};
            maxProducts[0] = minProducts[0] = nums[0];
            for(int i = 1; i < size; ++i)
            {
                maxProducts[i] = max(maxProducts[i-1]*nums[i], max(minProducts[i-1]*nums[i], nums[i]));
                minProducts[i] = min(maxProducts[i-1]*nums[i], min(minProducts[i-1]*nums[i], nums[i]));
                maxProduct = max(maxProduct, maxProducts[i]);
            }
            return maxProduct;
        }
    
        //actually we only need two variables to record the
        //previous min and max products;
    	int maxProduct(vector<int>& nums) 
        {
            int size = nums.size();
            int minProduct = nums[0], maxProduct = nums[0], ret = nums[0];
            for(int i = 1; i < size; ++i)
            {
                if(nums[i] < 0) swap(minProduct, maxProduct);
                maxProduct = max(maxProduct*nums[i], nums[i]);
                minProduct = min(minProduct*nums[i], nums[i]);
                ret = max(ret, maxProduct);
            }
            return ret;
        }
    
        //another solution using constant space too;
        //traversing from left to right and meantime from right to left
        //to calculate the possible max products since the subsequence will be 
        //from left to right or right to left anyway but in two directions 
        //in case of neglecting the other half;
        int maxProduct(vector<int>& nums) 
        {
            int lProduct = 1, rProduct = 1;
            int size = nums.size(), maxProduct = nums[0];
            for(int i = 0; i < size; ++i)
            {
                lProduct *= nums[i];
                rProduct *= nums[size-i-1];
                maxProduct = max(maxProduct, max(lProduct, rProduct));
                if(lProduct == 0) lProduct = 1;
                if(rProduct == 0) rProduct = 1;
            }
            return maxProduct;
        }
    };

  • 0

    I like the second solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.