O(n) Java DP solution


  • 4
    S
        public int maxProduct(int[] A) {
        	int po = 0, ne = 0, res = A[0];
            
        	for(int i=0; i<A.length;i++){
        		if(A[i]>0){
        			po = (po*A[i]>A[i]) ? po*A[i]:A[i];
        			ne = ne * A[i];
        			if(po > res)	res = po;
        		}else if(A[i]<0){
        			int buff = ne;
        			ne = (po*A[i]>A[i]) ? A[i]:po*A[i];
        			po = buff * A[i];
        			if(po!=0 && po > res)	res = po;
        		}else if(A[i] == 0){
        			po = 0; ne = 0;
        			if(res < 0)		res = 0;
        		}
        	}
        	return res;
        }

Log in to reply
 

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