Maximum Subarray Products

Question

Here is the problem and the code (I was looking for solutions, and most of them are similar, one post is easy to read), my question is 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 how

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

Find a continuous subarak in the array (containing at least one number) that has the largest product.

For example, given the array [2,3, -2,4], the adjacent 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

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

When you consider A[i]individually, you basically consider the sequence starting with A[i].

, imin imax A[0].

imin.

:

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

: imin = -4, imax = -4

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

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

So A[i] , imax , A[i] - .

Answer 2

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

}

:

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