My c++ solution,O(1) space, 10ms


  • 0
    J
    int maxProduct(int A[], int n) {
    	if(n<1){
    		return 0;
    	}
    	int maxPro=INT_MIN;
    	int tmax =0;
    	int lastMaxNegativePro=1;
    	int lastMaxPro=1;
    	int curMaxPro=0;
    	int curMaxNegativePro=0;
    	for(int i=0;i<n;i++){
    		if(A[i]<0){
    			curMaxNegativePro = A[i] <= lastMaxPro*A[i] ? A[i]:lastMaxPro*A[i];
    			curMaxPro = A[i] >= lastMaxNegativePro*A[i]?A[i]:lastMaxNegativePro*A[i];
    		}else{
    			curMaxNegativePro = A[i] <= curMaxNegativePro*A[i]?A[i]:curMaxNegativePro*A[i];
    			curMaxPro = A[i] >= lastMaxPro*A[i]?A[i]:lastMaxPro*A[i];
    		}
    		tmax = curMaxPro > curMaxNegativePro ?curMaxPro:curMaxNegativePro;
    		if(tmax>maxPro)
    			maxPro = tmax;
    
    		lastMaxNegativePro = curMaxNegativePro < 0?curMaxNegativePro:0;
    		lastMaxPro =curMaxPro > 0? curMaxPro:0;
    	}
    	return maxPro;
    }

Log in to reply
 

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