最大的subArray产品使用分而治之有人吗？

Question

我知道当涉及到整数数组时，这是最常见的编码问题之一。我正在寻找一种解决方案，以解决在数组中找到最长的连续subArray产品的问题，但使用分而治之的方法。

我将我的输入数组分成两部分:左数组和右数组递归求解，以防解决方案完全落在半数组中。我遇到的问题是subArray穿过数组的中点的情况。下面是我处理交叉点的函数的一小段代码：

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);
    }

处理整个搜索的函数包含以下内容：

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

//.更多代码.

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

最后，我只计算了三种情况下的最大乘积:左数组，交叉数组，右数组。

我仍然有几个角落案例失败。我的问题是，如果这个问题允许一个分而治之类型的递归解决方案，如果有人能发现我在代码中可能做错了什么，我将非常感谢任何可以帮助我摆脱困境的提示。

谢谢，阿敏

Answer 1

请看leetcode中的这些代码

C++分而治之

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