Sharing my solution: O(1) space, O(n) running time


  • 243
    R
    public int maxProduct(int[] A) {
        if (A.length == 0) {
            return 0;
        }
        
        int maxherepre = A[0];
        int minherepre = A[0];
        int maxsofar = A[0];
        int maxhere, minhere;
        
        for (int i = 1; i < A.length; i++) {
            maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]);
            minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]);
            maxsofar = Math.max(maxhere, maxsofar);
            maxherepre = maxhere;
            minherepre = minhere;
        }
        return maxsofar;
    }
    

    Note:
    There's no need to use O(n) space, as all that you need is a minhere and maxhere. (local max and local min), then you can get maxsofar (which is global max) from them.

    There's a chapter in Programming Pearls 2 that discussed the MaxSubArray problem, the idea is similar.


  • 0
    K

    DP doesn't work if the array contains not only interges, right?


  • 0
    R

    Hi. I think DP should still work with non-integers. Need to make sure the product is getting larger for maxhere and smaller for minhere (so abs value needs to be > 1).

    Don't have a proof at hand, so please let me know if you disagree.


  • 3
    D

    O(n), O(1) - space , the idea is to turn on one more product track after first negative num:

     public int maxProduct(int[] A) {
        int productAfterFirstNegative = Integer.MIN_VALUE;
        int allProduct = 1;
        int res = Integer.MIN_VALUE;
    
        for (int i : A) {
            if (i == 0) {
                res = Math.max(0, res);
                productAfterFirstNegative = Integer.MIN_VALUE;
                allProduct = 1;
            } else {
                allProduct *= i;
                res = Math.max(allProduct, res);
    
                if (productAfterFirstNegative == Integer.MIN_VALUE && i < 0) {
                    productAfterFirstNegative = 1;
                    continue;
                }
    
                if (productAfterFirstNegative != Integer.MIN_VALUE) {
                    productAfterFirstNegative *= i;
                    res = Math.max(productAfterFirstNegative, res);
                }
            }
        }
        return res;
    }

  • 0
    K

    I think you are right, maxhere picks local maximum, thanks.


  • 0
    L

    Your code is great, but every step you do two multiplications.

    Actually, we only need to record the product of all elements before first negative (start from head of array or last 0 element before the first negative) and first negative.

    So when we reach the end of array or a 0 element, we only need to check the all product, if it's negative, divide the value we recorded. (It's actually the product of all elements after first negative element, notice we need to check whether there's any element after the first negative element, otherwise we may get a 1 by mistake).


  • 0
    Q

    left.peter,
    I am thinking of the same way you mentioned. It passed.


  • 69
    P

    My idea is the same as yours, although I check if A[i] is positive before getting maxhere and minhere

     int maxProduct(int A[], int n) {
        if (n == 0) return 0;
        int maxProduct = A[0];
        int minProduct = A[0];
        int maxRes = A[0];
        for (int i = 1; i < n; i++)
        {
            if (A[i] >= 0)
            {
                maxProduct = max(maxProduct * A[i], A[i]);
                minProduct = min(minProduct * A[i], A[i]);
            }
            else
            {
                int temp = maxProduct;
                maxProduct = max(minProduct * A[i], A[i]);
                minProduct = min(temp * A[i], A[i]);
            }
            maxRes = max(maxRes, maxProduct);
        }
        return maxRes;
    }

  • 1
    L

    My solution by iterating forward and backward

    class Solution {
    public:
        int maxProduct(int A[], int n) {
            int currProd = 0, ret = INT_MIN;
            bool newStart = true;
            int i = -1;
            while (++i < n) {
                if (A[i] == 0) {
                    ret = max(ret, 0);
                    newStart = true;
                } else if (newStart) {
                    currProd = A[i];
                    ret = max(currProd, ret);
                    newStart = false;
                } else {
                    currProd *= A[i];
                    ret = max(currProd, ret);
                }
            }
            newStart = true;
            while (--i >= 0) {
                if (A[i] == 0) {
                    ret = max(ret, 0);
                    newStart = true;
                } else if (newStart) {
                    currProd = A[i];
                    ret = max(currProd, ret);
                    newStart = false;
                } else {
                    currProd *= A[i];
                    ret = max(currProd, ret);
                }
            }
            return ret;
        }
    };

  • 0
    H

    My AC answer.

    int maxProduct( int A[], int n ) {
    vector<int> positives = vector<int>( n, 0 );
    vector<int> negatives = vector<int>( n, 0 );

        int res = A[n - 1];
        positives[n - 1] = res > 0 ? res : 0;
        negatives[n - 1] = res < 0 ? res : 0;
        
        for ( int i = n - 2; i >= 0; i-- ) {
            if ( A[i] > 0 ) {
                positives[i] = positives[i + 1] > 0 ? A[i] * positives[i + 1] : A[i];
                negatives[i] = negatives[i + 1] < 0 ? A[i] * negatives[i + 1] : 0;
            } else if ( A[i] < 0 ) {
                positives[i] = negatives[i + 1] < 0 ? A[i] * negatives[i + 1] : 0;
                negatives[i] = positives[i + 1] > 0 ? A[i] * positives[i + 1] : A[i];
            }
            
            if ( positives[i] > res ) {
                res = positives[i];
            }
        }
        
        return res;
    }

  • 0
    B
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    D

    With above solution, the result for below input is 4 :
    int[] a = {-3, 4, 0, -1, 3, 0, -1, 2};


  • 0
    D

    Great thinking, only remind that if A contains not only integers, this will not work.

    For example: [1, -1, 0.1, 100], this alg will produce 10 instead of 100


  • 0
    C

    I remember that chapter is in Programming Pearl 1.I am so discouraged for fail in solving this problem,as I did read that chapter before. How can we apply that idea to this problem?


  • 7
    P
    public int maxProduct(int[] nums) {
            int max = nums[0], maxToHere = nums[0], minToHere = nums[0];
            for (int i = 1; i < nums.length; i++) {
                int temp = maxToHere;
                maxToHere = Math.max(Math.max(minToHere * nums[i], maxToHere * nums[i]), nums[i]);
                minToHere = Math.min(Math.min(minToHere * nums[i], temp * nums[i]), nums[i]);
                max = Math.max(max, maxToHere);
            }
            return max;
       }

  • 0
    C

    But this method doesn't fit for the case where the input has float number, correct? So is there any better way that O(n^2) method when float number could be in the array list.?


  • 6

    I prefer your clear idea since it's more readable. Here's my AC Java code.

    public static int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;
        int maxEndHere = nums[0];
        int minEndHere = nums[0];
        int maxSoFar = nums[0];
    
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num >= 0) {
                maxEndHere = Math.max(maxEndHere * num, num);
                minEndHere = Math.min(minEndHere * num, num);
            } else {
                int temp = maxEndHere;
                maxEndHere = Math.max(minEndHere * num, num);
                minEndHere = Math.min(temp * num, num);
            }
            maxSoFar = Math.max(maxEndHere, maxSoFar);
        }
        return maxSoFar;
    }

  • 0
    T

    Your solution can not handle [-2,0,1,-10]. Correct me if I'm wrong


  • 0
    D

    Perfect readable answer


Log in to reply
 

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