My solution in JAVA, O(n)

• it's quite clumsy, but probably the idea is different from other people

basically because we don't have numbers between 0 and 1, so the absolute value of product always goes up as you add more numbers, unless u reach 0 or negative numbers. but if u have 2 negative numbers, you win again. and if u reach a zero, u can't include it anymore, and since we want continuous, all previous numbers are useless. so we can divide the entire array into SECTIONS by "0".
i.e.

something like
p p p p n p p p n pp 0 ppppp

here "n" means negative number, and "p" means positive. in the code, in the inner while loop, I look at one section cut off by 0, and this section is divided into sections by "n", once I get 2 negative numbers, I roll them up into "section" again, and compare against the remaining.

in cases like "-1 -2 -3", I may get -1 * -2 = 2, = section1, and -3 , and get max 2

to guard against such cases, I compute again from right to left, and get -1 , (-2 * -3) , which 6

``````public class Solution {
public int maxProduct(int[] A) {
if (A.length == 0) return 0;
int best = maxProduct2(A);
int l = 0;int h = A.length-1;
while(l<h) {
int tmp = A[l];
A[l] = A[h];
A[h] = tmp;
l++;h--;
}
best = Math.max(best, maxProduct2(A));
return best;
}
public int maxProduct2(int[] A) {
int i=0;
int best = Integer.MIN_VALUE;
while(i<A.length) {
int section =1 ;
int sectionLen = 0;
int section1=1 ;
int section1Len = 0;
int sectionCnt = 0; // how many CLOSED sections we have seen
int lastNeg = 1;
while(i<A.length && A[i]!=0) {
if (A[i] > 0) {
section *= A[i];
sectionLen ++;
} else { // <0
if (sectionCnt == 0) {
sectionCnt = 1;
section1 = section;
section1Len = sectionLen;
section = 1;
sectionLen = 0;
lastNeg = A[i];
} else {
section *= -A[i] * section1 * (-lastNeg);
sectionCnt = 0;
sectionLen = 2;
}
}
i++;
}

if (sectionCnt == 1 )
if (section1Len > 0) {
best = Math.max(best, section1);
} else {
best = Math.max(best, lastNeg);
}
if (sectionLen > 0 )
best = Math.max(best, section);
if (i < A.length) {
// A[i] must be 0
best = Math.max(best, 0);
i++;
}

}

return best;
}
``````

}

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