Clear DP solution, confused by the time cost


  • 0
    I

    I am confused by the time cost of my two solutions.
    In the first one I use two vectors to save information and in the second one I just use 4 integers to do the same work. The idea is very similar to shinichish's solution

    The first version is shown as followed:

    Code in this version costs 20ms

    int maxProduct(int A[], int n) {
        if(!n) return 0;
        int product = 0;
        vector<int> maxVal(n, 0);
        vector<int> minVal(n, 0);
        maxVal[0] = minVal[0] = A[0];
        for(int i=1; i<n; i++) {
            maxVal[i] = max(A[i], max(A[i]*maxVal[i-1], A[i]*minVal[i-1]));
            minVal[i] = min(A[i], min(A[i]*maxVal[i-1], A[i]*minVal[i-1]));
        }
        int result = INT_MIN;
        for(int i : maxVal)
            result = max(result, i);
        return result;
    }
    

    Then I prove my code and replace the vectors with 4 integers. Thus in this version the memory complexity is O(1).

    Code in this version costs 40ms

    int maxProduct(int A[], int n) {
        if(!n) return 0;
        int lastMaxVal = A[0], lastMinVal = A[0], maxPro = A[0];
        int curMaxVal, curMinVal;
        for(int i=1; i<n; i++) {
            curMaxVal = max(A[i], max(A[i]*lastMaxVal, A[i]*lastMinVal));
            curMinVal = min(A[i], min(A[i]*lastMaxVal, A[i]*lastMinVal));
            lastMaxVal = curMaxVal; lastMinVal = curMinVal;
            maxPro = max(maxPro, curMaxVal);
        }
        return maxPro;
    }
    

    Why did it happened?? Could you please help me with it?


  • 0
    A

    I don't think this is possible


Log in to reply
 

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