使用分而治之的最大子数组产品有人吗？

Question

我知道这是整数数组中最常见的编码问题之一。我正在寻找解决在数组中查找最长连续子数组产品的问题，但使用分而治之的方法。

我将我的输入数组分成两半：递归求解左右数组，以防解完全落在半数组中。我遇到问题的地方是 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;

最后，我只是计算了 3 个场景的最大乘积：左数组、交叉数组、右数组。

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

谢谢，胺

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

使用分而治之的最大子数组产品有人吗？

Maximum subArray product using Divide and Conquer Anyone?

algorithm

divide-and-conquer

sub-array