A quite direct but clumsy O(n) solution in C. Just have a look...

• #ATTENTION:

THIS IS A STUPID SOLUTION, SIMPLE BUT NOT CONCISE, CLUMSY BUT QUITE DIRECT

A quick description:

0 - Absolutely, more numbers means bigger absolute value. The trap is : `zero` & `negative numbers`

Key point is splitting the array into 3 parts( by negative numbers):

head(no negative numbers), middle, tail(same as head); The format is:`[head, negnum1, middle, negnum2, tail]`

e.g.1`[1, 2, 3, -1, 4, 5, 6, -2, 7, 8] ——> [1*2*3, -1, 4*5*6, -2, 7*8] ——> [6,-1,120,-2,56] ——>`

because `middle` is positive, so we can add both tail and head into product: `6*-1*120*-2*56`

e.g.2 `[1,2,-1,-4,-5,-6,-2,7,8] ——> [2,-1,-120,-2,56]——>`

because `middle` is negative &&`|2*-1|<|-2*56|`, so choose: `[-120, -2, 56] ——> -120*-2*56` as result.

e.g.3 `[A,0,B]`——> deal with `[A]`, then deal with `[B]`——>

return `max(A.max_product, B.max_product)`

##STEPS

1 - filter zeros use `maxProduct()`, for example: split the array `[A,0,B,0,C]` into `[A], [B], [C]`

2 - deal with sub-problem `[A], [B], [C]`in `max_no_zeor()`

3 - in `max_no_zero()` we do:

1- scan from head, find a negative number `A[negindex_front]` [e.g. number = -1]

2 - scan from tail, find a negative number `A[negindex_back]` [e.g. number = -2]

3 - calculate the product between `negindex_front` and `negindex_back`

now we get somethin like this: `[product_head, -1, product_middle, -2, product_tail]`

only 5 numbers... you know what to do....

##Oh... after unlocking the answer, I realized how stupid it is!
##Anyway, not very hard to understand
this is the code:

``````int max(int a,int b){return a>b?a:b;}
int max_no_zero(int *A,int start, int end){
/*void arr*/
if(end==start)
return INT_MIN;
/*only one element*/
if(end==start+1)
return A[start];
/*calcu from front*/
int front_pro = 1, negindex_front;
for(negindex_front=start;negindex_front<end;negindex_front++){
if(A[negindex_front]<0)
break;
front_pro *= A[negindex_front];
}
/*if no negative number*/
if(negindex_front==end)
return front_pro;
/*calcu from back*/
int back_pro = 1,negindex_back;
for(negindex_back=end-1;negindex_back>start-1;negindex_back--){
if(A[negindex_back]<0)
break;
back_pro *= A[negindex_back];
}
/*if only one negative number*/
if(negindex_front==negindex_back)
return max(front_pro,back_pro);
/*calcu middle*/
int middle_pro = 1;
for(int i=negindex_front+1;i<negindex_back;i++)
middle_pro *= A[i];
if(middle_pro>0)
return front_pro*A[negindex_front]*middle_pro*A[negindex_back]*back_pro;
else if(middle_pro==0)
return 0;
else{
int multi = max(front_pro*A[negindex_front]*-1,back_pro*A[negindex_back]*-1);
return multi*middle_pro*-1;
}
}

int maxProduct(int A[], int n) {
int start = 0,end;
int max_pro = A[0];
int zero_exist = false;
while(start<n){
for(end=start;end<n;end++){
if(A[end]==0){
zero_exist = true;
break;
}
}
max_pro = max(max_pro,max_no_zero(A,start,end));
start = end+1;
}
if(max_pro<0&&zero_exist)
return 0;
else
return max_pro;
}``````

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