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

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

Divide and conquer, recursively divide the array into two parts on the middle point. When combine, start from the joint place of two sub-arrays then assign a left pointer to move to left until arrive the start of left sub-array and right pointer move to right until arrive the end of the right sub-array.

For example,
[2, 3     <-LP | RP->    -2, 4]

In every combine we compute the max value of  left sub array max, right sub array max, and the multiply of the pointers iterated area.

Solution:


class Solution {
public:
        int mergeTwoMax(vector<int>& nums, int lMax, int rMax, int l1, int r1, int l2, int r2)
        {
                int tempLMax = 1 << 31, tempRMax = 1 << 31;
                int tempLMin = 1 << 31 - 1, tempRMin = 1 << 31 - 1, sum = 1;
                for(int i = r1; i >= l1; --i) 
                {
                        sum *= nums[i];
                        if(tempLMax < sum) tempLMax = sum;
                        if(tempLMin > sum) tempLMin = sum;
                }
                sum = 1;
                for(int i = l2; i <= r2; ++i)
                {
                        sum *= nums[i];
                        if(tempRMax < sum) tempRMax = sum;
                        if(tempRMin > sum) tempRMin = sum;
                }
                return max(tempLMax * tempRMax, 
                    max(tempLMin * tempRMin,max(lMax, rMax)));
        }
    
        int recursiveMax(vector<int>& nums, int l, int r)
        {
                if(r == l) return nums[l];
                if(r - l == 1) return max(nums[l] * nums[r], max(nums[l], nums[r]));
        
                int l1 = l, r1 = (r + l) / 2;
                int l2 = r1 + 1, r2 = r;
        
                return mergeTwoMax(nums, recursiveMax(nums, l1, r1), 
                    recursiveMax(nums, l2, r2), l1, r1, l2, r2);
       }
    
        int maxProduct(vector<int>& nums) {
        
                if(nums.size() == 0) return 1 << 31;
                return recursiveMax(nums, 0, nums.size() - 1);
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *