# Java O(n) solution without DP

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);
}``````

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