Divide and conquer approach in C. Just for fun.


  • 0
    E
    int findMaxProduct(int*, int, int);
    int findMaxCrossingProduct(int*, int, int, int);
    
    int maxProduct(int* nums, int numsSize) {
        return findMaxProduct(nums, 0, numsSize-1);
    }
    
    int findMaxProduct(int* nums, int low, int high) {
        if (low == high) {
            return nums[low];
        }
        else {
            int mid = (low + high) / 2;
            int maxLeft, maxRight, maxCross;
            
            maxLeft  = findMaxProduct(nums, low, mid);
            maxRight = findMaxProduct(nums, mid+1, high);
            maxCross = findMaxCrossingProduct(nums, low, mid, high);
            
            return ((maxCross > maxLeft && maxCross > maxRight) ? maxCross :
                    (maxLeft > maxRight ? maxLeft : maxRight));
        }
    }
    
    int findMaxCrossingProduct(int* nums, int low, int mid, int high) {
        int leftMax, rightMax, max;
        int leftMin, rightMin, min;
        int i;
        
        leftMax = leftMin =nums[mid];
        max = min = 1;
        for (i = mid; i >= low; i--) {
            max *= nums[i];
            min *= nums[i];
            if (max > leftMax) {
                leftMax = max;
            }
            if (min < leftMin) {
                leftMin = min;
            }
        }
        
        rightMax = rightMin = nums[mid+1];
        max = min = 1;
        for (i = mid+1; i <= high; i++) {
            max *= nums[i];
            min *= nums[i];
            if (max > rightMax) {
                rightMax = max;
            }
            if (min < rightMin) {
                rightMin = min;
            }
        }
        
        max = leftMax * rightMax;
        min = leftMin * rightMin;
        
        return (max > min ? max : min);
    }

Log in to reply
 

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