# 2ms JAVA O(1) space O(n) time solution

• Thinking procedure:
If an array contains all positive numbers, then the subarray would be itself.

For arrays which have negative numbers:
For example, array a = [-1,2,3,4,-2,3,2,-1,3,-2,3,2,-1], there are five negative numbers in this array.

Those negative numbers' positions are 0,4,7,9,12

Suppose p(x,y) is the product of a[x]*...*a[y], we need to compare following products of subarrays(all have positive results):
p(0,4)
p(0,11) = P(0,4)*p(4,7)*p(7,11) /(a[4]*a[7])
p(1,7)
p(1,12) = p(1,7)*p(7,9)*p(9,12) /(a[7]*a[9])
P(7,11)
p(9,12)

Since all the numbers are integer, p(0,11) >= {p(0,4), p(4,7), p(7,11)}, p(1,12) >= {p(1,7),p(7,9),p(9,12)}. The question now becomes comparing the two largest contiguous subarrays. So we just need to calculate p(0,11) and p(1,12).

We know that p(1,12) = p(0,12)/a[0]. In order to get p(1,12), we just need two variables to store the maximum negative product and minimum negative product separately.

For arrays which contain 0, each 0 will split the arrays apart. We calculate each part to get the result.

``````    public int maxProduct(int[] nums) {
int len = nums.length;
if(len == 1) return nums[0];
int res = 0;
int maxP = 0, maxN = Integer.MIN_VALUE, minN = 0;
int tmp = 1, curMax = 0;
for(int i = 0; i < len; i++){
if(nums[i] == 0){
int cur = minN/maxN;
curMax = maxP>cur? maxP:cur;
if(curMax > res) res = curMax;
tmp = 1;
maxP = 0;
maxN = Integer.MIN_VALUE;
minN = 0;
continue;
}
tmp *= nums[i];
if(tmp > maxP){
maxP = tmp;
}
if(tmp<0 && maxN == Integer.MIN_VALUE){
maxN = tmp;
}
else if(tmp < minN){
minN = tmp;
}
}
int cur = minN/maxN;
curMax = maxP>cur? maxP:cur;
if(curMax > res)res = curMax;
return res;
}
``````

• What if there are float numbers? I know there aren't float numbers in test cases but this method is not generic

• @yunwwww The input provided by this problem are int[], not float[]. If there are float numbers, then things become complicated.

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