Maximum Product Subarray issue

Question

Here is the problem and code (I searched for solutions and most are similar, post one easy to read), my question is for below two lines,

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

why we need to consider A[i] individually and why not just write as,

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

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 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;
}

thanks in advance, Lin

Answer 1

public class MaximumContiguousSubArrayProduct {
    public static int getMaximumContiguousSubArrayProduct(final int... array) {
        if (array.length == 0) {
            return -1;
        }
        int negativeMax = 0, positiveMax = 0, max;
        if (array[0] < 0) {
            negativeMax = array[0];
            max = negativeMax;
        } else {
            positiveMax = array[0];
            max = positiveMax;
        }

        for (int i = 1; i < array.length; i++) {
            if (array[i] == 0) {
                negativeMax = 0;
                positiveMax = 0;
                if (max < 0) {
                    max = 0;
                }
            } else if (array[i] > 0) {
                if (positiveMax == 0) {
                    positiveMax = array[i];
                } else {
                    positiveMax *= array[i];
                }
                if (negativeMax != 0) {
                    negativeMax *= array[i];
                }
                if (positiveMax > max) {
                    max = positiveMax;
                }
            } else {
                if (array[i] > max) {
                    max = array[i];
                }
                if (negativeMax == 0) {
                    if (positiveMax != 0) {
                        negativeMax *= positiveMax;
                    } else {
                        negativeMax = array[i];
                    }
                    positiveMax = 0;
                } else {
                    if (positiveMax != 0) {
                        int temp = positiveMax;
                        positiveMax = negativeMax * array[i];
                        negativeMax = temp * array[i];
                    } else {
                        positiveMax = negativeMax * array[i];
                        negativeMax = array[i];
                    }

                    if (positiveMax > max) {
                        max = positiveMax;
                    }
                }
            }
        }
        return max;
    }

}

Corresponding tests:

import org.junit.Test;

import static org.hamcrest.CoreMatchers.equalTo;
import static org.hamcrest.MatcherAssert.assertThat;

public class MaximumContiguousSubArrayProductTest {
    @Test
    public void testMaximumProductSubArray() {
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(2, 3, -2, 4), equalTo(6));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(2, 3, -2, 4, 9), equalTo(36));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(-2, 0, -1), equalTo(0));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(), equalTo(-1));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(-1), equalTo(-1));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(1), equalTo(1));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(-9, -3, -4, -1), equalTo(9 * 3 * 4));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(-1, 2), equalTo(2));
        assertThat(MaximumContiguousSubArrayProduct.getMaximumContiguousSubArrayProduct(-100, -1, 99), equalTo(9900));
    }
}

Answer 2

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

When you consider A[i] individually you are basically taking into account the sequence that begins at A[i].

You are doing a similar thing when you initialize the imin and imax by A[0] initially.

Same is true for the imin case.

Small Example:

Array = {-4, 3, 8 , 5}

Initialization: imin = -4, imax = -4

Iteration 1: i=1 , A[i]=3

imax = max(A[i], imax * A[i]); -> imax = max(3, -4 * 3); -> imax = 3

So A[i] can be maximum when imax is negative and A[i] is positive.