My simple C++ (not DP) accepted solution, any thought to make it more efficient?


  • 0
    H

    class Solution {
    public:
    int maxProduct(int A[], int n) {

    int* max = new int[n];
    int* min = new int[n];
    
    
    min[0]=A[0];
    max[0]=A[0];
    int i;
    for ( i=1; i<n;i++){
    
    	if (A[i]>0){
    	max[i]= (A[i]*max[i-1]>A[i])? A[i]*max[i-1] : A[i];
    	min[i]= (A[i]*min[i-1]<A[i])? A[i]*min[i-1] : A[i];
    	}
    	else{
    			max[i]= (A[i]*min[i-1]>A[i])? A[i]*min[i-1] : A[i];
    			min[i]= (A[i]*max[i-1]<A[i])? A[i]*max[i-1] : A[i];
    	}
    
    		
    }
    int ans=max[0];
    for (int j=0;j<i;j++)
    {
    	if (max[j]>ans) {ans=max[j];}
    }
    
    return (ans);
    

    }
    };


  • 1
    W

    Of course, the code can be more efficient.

    When calculating max[i], we just use max[i - 1] and min[i - 1], and the same to min[i]. So the max and min array is redundant.

    It should be noticed that when 'A[i] < 0', we should keep the previous max[i - 1] first.

    Here is a more concise code based on your idea.

    class Solution {
    public:
        int maxProduct(int A[], int n) {
            int ret, maxP, minP;
    		ret = maxP = minP = A[0];
    		for (int idx = 1; idx < n; ++idx) {
    			if (A[idx] > 0) {
    				maxP = max(maxP * A[idx], A[idx]);
    				minP = min(minP * A[idx], A[idx]);
    			}
    			else {
    				int temp = maxP;
    				maxP = max(minP * A[idx], A[idx]);
    				minP = min(temp * A[idx], A[idx]);
    			}
    			if (maxP > ret) {
    				ret = maxP;
    			}
    		}
    		return ret;
        }
    };

Log in to reply
 

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