Java O(n) solution without DP


  • 0
    M
    1. Since the input array contains only integer, we could only consider
      when there's 0 and minus numbers.
    2. When we meet 0, we get the maximum product of the subarrays to the
      left and the right of 0 recursively and see whether they are all
      less than 0.
    3. When we meet minus numbers in an array without 0, we count the
      number of minus numbers. If it's even, we simply multiply all
      numbers and return. If it's odd, we simply decide to discard the
      numbers before the first one or after the last one. All middle parts
      should be kept
      .
    	private int getProduct(int[] nums, int start, int end) {
    		int product=1;
    		for (int i=start;i<end;i++)
    			product*=nums[i];
    		return product;
    	}
    	
    	private int maxProduct(int[] nums, int start, int end) {
    		if (start>=end)
    			return Integer.MIN_VALUE;
    		if (end-start==1)
    			return nums[start];
    		
    		int countZero=0, countMinus=0;
            for (int i=start;i<end;i++) {
            	if (nums[i]==0)
            		countZero++;
            	else if (nums[i]<0)
            		countMinus++;
            }
            
            if (countZero!=0) {
            	int[] zeroIndex=new int[countZero+2];
            	zeroIndex[0]=start-1;
            	for (int i=start,cur=1;i<end;i++)
            		if (nums[i]==0) {
            			zeroIndex[cur]=i;
            			cur++;
            		}
            	zeroIndex[zeroIndex.length-1]=end;
            	int max=Integer.MIN_VALUE;
            	for (int i=0;i<countZero+1;i++) {
            		int val=this.maxProduct(nums, zeroIndex[i]+1, zeroIndex[i+1]);
            		if (val>max)
            			max=val;
            	}
            	if (max<0)
            		return 0;
            	return max;
            }
            
            if (countMinus%2==0)
            	return this.getProduct(nums, start, end);
            
            int leftMinus=start,rightMinus=end-1;
            while (nums[leftMinus]>0)
            	leftMinus++;
            if (countMinus==1)
            	return Math.max(this.getProduct(nums, start, leftMinus), this.getProduct(nums, leftMinus+1, end));
            while (nums[rightMinus]>0)
            	rightMinus--;
            return this.getProduct(nums, leftMinus+1, rightMinus)*Math.min(this.getProduct(nums, start, leftMinus+1), this.getProduct(nums, rightMinus, end));
    	}
        public int maxProduct(int[] nums) {
            if (nums.length==0)
            	return 0;
            return this.maxProduct(nums, 0, nums.length);
        }

Log in to reply
 

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