An implementation of the suggested solution (dynamic programming)


  • 6
    Z
    int maxProduct(int A[], int n) {
        if(n == 0){
            return 0;
        }
        int* maxdp = new int[n];
        int* mindp = new int[n];
        maxdp[0] = A[0];
        mindp[0] = A[0];
        int maxProduct = A[0];
        for(int i = 1; i < n; i++){
            if(A[i] > 0){
                maxdp[i] = max(maxdp[i - 1] * A[i], A[i]);
                mindp[i] = min(mindp[i - 1] * A[i], A[i]);
            }
            else{
                maxdp[i] = max(mindp[i - 1] * A[i], A[i]);
                mindp[i] = min(maxdp[i - 1] * A[i], A[i]);
            }
            maxProduct = max(maxProduct, maxdp[i]);
        }
        return maxProduct;
    }

  • 0
    D

    thanks for sharing, but the suggested solution also mentioned that an array keeping track of the the local min&max is not necessary, instead, for each step we only need to know the pre-max&min, so two variables are sufficient


  • 0
    Z

    Yeah I think you are right. Thank you so much for advice.


  • 2
    D
    class Solution {
    

    public:
    int maxProduct(int A[], int n) {
    if (n <1 ) return 0;

        // assume no overflow, underflow
        int maxPro = A[0];
        int minPro = A[0];
        int res = A[0];
        for (int i = 1; i < n; i++){
            if(A[i] > 0) {
                maxPro = max(maxPro * A[i], A[i]);
                minPro = min(minPro * A[i], A[i]);
            } else { // covers A[i] = 0
                int temp = maxPro;  // !!! record the maxPro
                maxPro = max(minPro * A[i], A[i]);
                minPro = min(temp * A[i], A[i]);
            }
            if (maxPro > res) res = maxPro;
        }
        return res;
    }
    

    };


Log in to reply
 

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