# My solution - O(1) space O(n) time - just doing a summary

• observations:

1. the optimum sub-array has no 0 in it;
2. for an array with no 0, the optimum sub-array starts from either the first number or from the number after first negative number (the numbers in front of it constitutes the firs negative factor).

my approach:

1. break the array into chunks separated by zeros;
2. for each chunk, find the maximum value of 2 sequences products:
I. products of the contiguous sub-arrays starting from the 1st number of the chunk;
II. products of the contiguous sub-arrays starting from the number after the 1st negative number in the chunk;
3. the answer is the maximum of the results from all chunks and 0.

code:

``````class Solution {public:
int maxProduct(int A[], int n) {
int p1, p2, nn, max;
p1 = 1, nn = 0, max = A[0];
for(int i = 0; i < n; i++) {
if(A[i] == 0) {
p1 = 1;
nn = 0;
if(max < 0) max = 0;
} else {
p1 *= A[i];
if(p1 > max) max = p1;
if(nn) {
p2 *= A[i];
if(p2 > max) max = p2;
}
if(A[i] < 0 and !nn) {
p2 = 1;
nn = 1;
}
}
}
return max;
}
``````

};

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