数组中最大邻接积的打印子数组

Question

最大乘积子数组给定一个数组包含正整数和负整数，求最大乘积的子数组。例子：

public int maxProductSubArray(int arr[], int len) {

        int res = arr[0];

        int max = arr[0];
        int min = arr[0];

        for (int i = 1; i < len; i++) {

            int temp = max;

            max = Math.max(Math.max(max * arr[i], min * arr[i]), arr[i]);
            min = Math.min(Math.min(temp * arr[i], min * arr[i]), arr[i]);

            res = Math.max(res, max);
        }

        return res;

    }

但不能破题找到子数组。

Answer 1

通过分而治之可以有效地解决这个问题。

假设您想要解决子数组[l,r]的问题；然后，假设c=(l+r)/2，该解决方案要么是[l,c]中的子数组，要么是[c+1,r]中的子数组，或者是包含c和c+1的子数组。

然后定义一个函数f(l，r)，返回子段的答案；然后，要计算这个函数，首先递归调用f(l,c)和f(c+1,r)，并选择最大值作为临时答案。然后计算段的乘法[c,c]，然后[c-1,c]等等（使用[c-k,c]的乘法=[c-k+1,c]*数组[c-k])并计算所有这些段的最大乘法和最小乘法。对c([c+1,c+1]，[c+1,c+2]等等）右边的段执行相同的操作，然后，答案将是一个临时答案，即最大值的乘法或最小值的乘法或最小值和最大值的乘法，反之亦然（如果乘法为负数，则需要最小乘以最大值）。返回这四个值之间的最大值或临时答案作为函数结果。

如果有必要，不仅返回乘法函数的值，还可以返回到达这些值的段。

此解决方案使用θ（n log n)时间和θ（n）空间。