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

Since imax and imin both start life equal to r, your update proposal would keep the two values always equal. Not what you want. (You are aware, I hope, that the code you posted finds the largest product, not subarray itself--as required in the problem statement). — Ted Hopp
– Ted Hopp, Commented Nov 3, 2015 at 21:56
@TedHopp, do you think we can simplify code by using only imax = max (imin * A[i], max(A[i], imax * A[i])) and imin = min (imin * A[i], min(A[i], imax * A[i])), ad no need to use the if (A[i] < 0) check? Thanks. — Lin Ma
– Lin Ma, Commented Nov 3, 2015 at 22:20

pgiitu · Accepted Answer · 2015-11-03 22:05:31Z

1

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.

edited Nov 3, 2015 at 22:05

answered Nov 3, 2015 at 21:47

pgiitu

1,6691 gold badge15 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Ted Hopp Over a year ago

@LinMa - It certainly can when A[i] is negative and imin is positive! (-2 is larger than 3*-2, for instance).

pgiitu Over a year ago

@LinMa I have updated the answer with a small example where A[i] can be largest in a particular iteration.

Lin Ma Over a year ago

@pgiitu, nice sample!

pgiitu Over a year ago

@LinMa I hope you understand it now.

Lin Ma Over a year ago

@pgiitu, do you think we can simplify code by using only imax = max (imin * A[i], max(A[i], imax * A[i])) and imin = min (imin * A[i], min(A[i], imax * A[i])), ad no need to use the if (A[i] < 0) check? Thanks.

|

Coder93 · Accepted Answer · 2019-10-17 07:37:47Z

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

Collectives™ on Stack Overflow

Maximum Product Subarray issue

2 Answers 2

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related