Maximum subArray product using Divide and Conquer Anyone?

Question

I am aware that this is one of the most common coding questions when it comes to integral arrays. I am looking for a solution to the problem of finding the longest contiguous subArray product within the array, but using a Divide and Conquer approach.

I split my input array into two halves: the left and right arrays are solved recursively in case the solution falls entirely in the half array. Where I have a problem is with the scenario where the subArray crosses the mid-point of the array. Here is a short snippet of my code for the function handling the crossing:

pair<int,pair<int, int>> maxMidCrossing(vector<int>& nums, int low, int mid, int high)
    {
        int m = 1;
        int leftIndx = low;
        long long leftProduct = INT_MIN;

        for(int i = mid-1; i>= low; --i)
        {
            m *= nums[i];
            if(m > leftProduct) {
                leftProduct = m;
                leftIndx = i;
            }
        }
        
        int mleft = m;
        m=1;
        int rightIndx = high;
        long long rightProduct = INT_MIN;
        
        for(int i = mid; i<= high; ++i) 
        {
             m *= nums[i];
            if(m > rightProduct) {
                rightProduct = m;
                rightIndx = i;
            }
        }
        
        int mright = m;
        cout << "\nRight product " << rightProduct;
        pair<int, int> tmp;
        int maximum = 0;
        
        // Check the multiplication of both sides of the array to see if the combined subarray satisfies the maximum product condition. 

        if(mleft*mright < leftProduct*rightProduct) {
            tmp = pair(leftIndx, rightIndx);
            maximum = leftProduct*rightProduct;
        }
        
        else {
            tmp = pair(low, high);
            maximum = mleft*mright;
        }

        return pair(maximum, tmp);
    }

The function handling the entire search contains the following:

auto leftIndx = indexProduct(left);
    auto rightIndx = indexProduct(right);
    auto midResult = maxMidCrossing(nums, 0, mid, nums.size()-1); // middle crossing

//.....more code........

if(mLeft > midProduct && mLeft > mRight)
            tmp=leftIndx;
        
        else if (mRight > midProduct && mRight > mLeft)
             tmp = pair(rightIndx.first + mid, rightIndx.second + mid);
        
        else tmp=midIndx;

In the end, I just compute the maximum product across the 3 scenarios: left array, crossing array, right array.

I still have a few corner cases failing. My question is if this problem admits a recursive solution of the Divide and Conquer type, and if anyone can spot what I may be doing wrong in my code, I would appreciate any hints that could help me get unstuck.

Thanks, Amine

Answer 1

Take a look at these from leetcode

C++ Divide and Conquer

https://leetcode.com/problems/maximum-product-subarray/discuss/48289/c++-divide-and-conquer-solution-8ms

Java https://leetcode.com/problems/maximum-product-subarray/discuss/367839/java-divide-and-conquer-2ms

c# https://leetcode.com/problems/maximum-product-subarray/discuss/367839/java-divide-and-conquer-2ms