java - 最大乘积子阵列问题

这是问题和代码(我搜索了解决方案，大多数都相似，发布一个易于阅读的)，我的问题是以下两行，

 imax = max(A[i], imax * A[i]);
 imin = min(A[i], imin * A[i]);

为什么我们需要单独考虑 A[i] 以及为什么不写为，

 imax = max(imin * A[i], imax * A[i]);
 imin = min(imin * A[i], imax * A[i]);

找出具有最大乘积的数组(至少包含一个数字)中的连续子数组。

例如，给定数组 [2,3,-2,4]，
连续子数组 [2,3] 具有最大的乘积 = 6。

int maxProduct(int A[], int n) {
    // store the result that is the max we have found so far
    int r = A[0];

    // imax/imin stores the max/min product of
    // subarray that ends with the current number A[i]
    for (int i = 1, imax = r, imin = r; i < n; i++) {
        // multiplied by a negative makes big number smaller, small number bigger
        // so we redefine the extremums by swapping them
        if (A[i] < 0)
            swap(imax, imin);

        // max/min product for the current number is either the current number itself
        // or the max/min by the previous number times the current one
        imax = max(A[i], imax * A[i]);
        imin = min(A[i], imin * A[i]);

        // the newly computed max value is a candidate for our global result
        r = max(r, imax);
    }
    return r;
}

提前致谢，
林

最佳答案

imax = max(A[i], imax * A[i]);

当您单独考虑 A[i] 时，您基本上是在考虑从 A[i] 开始的序列。

当您最初通过 imin 初始化 imax 和 A[0] 时，您正在做类似的事情。
imin 情况也是如此。

小例子:
Array = {-4, 3, 8 , 5}
初始化:imin = -4, imax = -4
迭代 1:i=1 , A[i]=3imax = max(A[i], imax * A[i]); -> imax = max(3, -4 * 3); -> imax = 3
因此，当 A[i] 为负且 imax 为正时，A[i] 可以最大。

关于java - 最大乘积子阵列问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33509593/