NO DP, go through one time using stack(Java)


  • 0
    S
    public int maxProduct(int[] A) {
    		if(A.length == 0){return 0;}
    		Stack<Integer> stack = new Stack<Integer>();
    		Stack<Integer> index = new Stack<Integer>();
    
    		int begin = 0;
    		while(A[begin] == 0){
    			begin++;
    			if(begin > A.length-1){return 0;}
    		}
    		int max = A[begin];
    		int product = A[begin];
    		if(product < 0){stack.add(product);index.add(begin);}
    		for(int i = begin+1;i < A.length;i++){
    			if(A[i] < 0){
    				// check if max
    				if(product > max){max = product;}
    				stack.add(product*A[i]);
    				index.add(i);
    				product *= A[i];
    			}else if(A[i] == 0){
    				// check if max
    				if(0 > max){max = 0;}
    				if(product > max){max = product;}
    				while(!stack.isEmpty()){
    					int cur = stack.pop();
    					int cur_index = index.pop();
    					if(i-1 != cur_index){
    						if(product/cur > max){max = product/cur;}
    					}
    				}
    				while(A[i] == 0){
    					i++;
    					if(i >= A.length-1){break;}
    				}
    				if(i <= A.length-1){
    					if(A[i] < 0){
    						stack.add(A[i]);
    						index.add(i);
    					}
    					product = A[i];
    				}
    			}else{
    				product *= A[i];
    			}
    		}
    		if(product > max){max = product;}
    		while(!stack.isEmpty()){
    			int cur = stack.pop();
    			int cur_index = index.pop();
    			if(A.length-1 != cur_index){
    				if(product/cur > max){max = product/cur;}
    			}
    		}
    
    		return max;
    }
    private int max(int a,int b){
    		return a > b?a:b;
    	}

Log in to reply
 

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