Ac solution code


  • 0

    This is a simplified DP solution:

    max, min: The maximum and minimum product among the subarrays whose last element is A[i]
    
    For each A[i]:
       1) If A[i] is positive 
           max = Math.max(max * A[i], A[i]);
           min = Math.min(min * A[i], A[i]);
       2) If A[i] is negative 
    	   max = Math.max(min * A[i], A[i]);
    	   min = Math.min(max * A[i], A[i]); 
       res = Math.max(res, max); 
    

    Runtime complexity = O(n); Extra Space = (1)

    JAVA Code:

    public int maxProduct(int[] A) {
    	int min = A[0], max = A[0];// max, min: The maximum and minimum product among the subarrays whose last element is A[i].
    	int res = A[0];
    	for (int i = 1; i < A.length; i++) {
    		if (A[i] > 0) {// A[i] is positive 
    			max = Math.max(max * A[i], A[i]);
    			min = Math.min(min * A[i], A[i]);
    		} else {// A[i] is negative
    			int maxTmp = max;
    			max = Math.max(min * A[i], A[i]);
    			min = Math.min(maxTmp * A[i], A[i]);
    		}
    		res = Math.max(res, max);
    	}
    	return res;
    }

Log in to reply
 

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