C++ solution by using divide and conquer


  • 0
    F

    The idea behind this was exactly borrowed from the similar problem Maximum Subarray, and porker2008 had made a great explanation

    Thought this approach is not effective(only beat 8% cppsubmisssions ), it gives us another way to think.

    class Solution {
    public:
        int maxProduct(vector<int>& a) {
            return maxProductHelper(a, 0, a.size()-1);
        }
        int maxProductHelper(vector<int>& a, int left, int right) {
            if (right == left) return a[right];
            // use divide and conquer
            int middle = (left + right) / 2;
            // case 1: max product subarray contains the middle element
            int leftMax = a[middle];
            int leftMin = a[middle];
            int rightMax = a[middle+1];
            int rightMin = a[middle+1];
            int i;
            int tmp = a[middle];
            for(i=middle-1; i>=left; i--) {
                tmp *= a[i];
                if (tmp>leftMax) leftMax = tmp;
                if (tmp<leftMin) leftMin = tmp;
            } 
            tmp = a[middle+1];
            for(i=middle+2; i<=right; i++) {
                tmp *= a[i];
                if(tmp>rightMax) rightMax = tmp;
                if(tmp<rightMin) rightMin = tmp;
            }
            int middleAns = max(leftMax*rightMax, leftMin*rightMin);
            // case 2.1: not contain the middle element, subarray elements all in left 
            int leftAns = maxProductHelper(a, left, middle);
            // case 2.2: not contain the middle element, subarray elements all in right
            int rightAns = maxProductHelper(a, middle+1, right);
            // calculate above 3 cases and return the maximum one
            return max(max(leftAns, rightAns), middleAns);
        }
    };
    

Log in to reply
 

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