Possibly simplest solution with O(n) time complexity

  • 321
    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;

  • 9

    I think you might forget the situation in which there might have zero in the array. In this circumstance, you code might be wrong.

  • 12

    the code can deal with such situation. for zero value, imax and imin must be both zero because zero times any number is zero. please refer to the definitions of imax and imin.

  • 4

    +1 for this clean DP solution

  • 1

    beautiful :)

  • 1

    it is beautiful!

  • 62

    very nice . I guess a bit of more explanation would help people understand:

    this is very similar to the " max cumulative sum subarray" problem. here you keep 2 values: the max cumulative product UP TO current element starting from SOMEWHERE in the past, and the minimum cumuliative product UP TO current element . it would be easier to see the DP structure if we store these 2 values for each index, like maxProduct[i],minProduct[i] .

    at each new element, u could either add the new element to the existing product, or start fresh the product from current index (wipe out previous results), hence the 2 Math.max() lines.

    if we see a negative number, the "candidate" for max should instead become the previous min product, because a bigger number multiplied by negative becomes smaller, hence the swap()

  • 1

    brilliant for swapping!

  • 0

    Awesome idea, thanks for sharing!

  • 0

    The swapping part is nice !

  • 0

    Very neat yet precise explanation. But it seems a theoretical proof is needed here, otherwise, it's hard to understand this method intuitively.

  • 0

    This is a code from God~, especially for the swap part.

  • 0

    I don't fully understand the code

  • 0

    Awesome code. My code is something like below:

    M[i] the maximal product ending at i'th element
    N[i] the minimal product ending at i'th element

    M[i] = max (A[i], A[i] > 0 ? A[i] * M[i-1] : A[i] * N[i-1])
    N[i] = min (A[i], A[i] > 0 ? A[i] * N[i-1] : A[i] * M[i-1])

    But your code to swap M[i] and N[i] is much cleaner.

  • 0

    awesome solution
    How do you come up with this solution ?

  • 0

    dones't work for [-2, 3, -4]

  • 0

    @sonakshi4 it totally works. The answer is 24. BTW, OP this is so beautiful!!!

  • 0

    Just sign up to upvote your post, this code is just so elegant

  • 1

    wow...i didnt think it to be this easy....great solution

  • 0

    Awesome solution , what a clean DP structure!
    The swap is quite smart.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.