# A naive but straigtforward solution

• When encounter a 0, split the sequence and get the max of the left, right, and 0.
If the accumulative result is negative, check two cases: 1. divide out the elements from left till the first
negative element. 2. divide out the elements from right till the first negative element. Return the max result.

``````int helper(int A[], int l, int r) {
if (l > r) {
return INT_MIN;
}

if (l == r) {
return A[l];
}

int max_prod = INT_MIN;
int acc = 1;
for (int i = l; i <= r; ++i) {
if (A[i] == 0) {
return max(helper(A, l, i - 1), max(0, helper(A, i + 1, r)));
}
acc *= A[i];
max_prod = max(max_prod, acc);
}

// find first negtive number from left and divide out elements before it (including itself).
if (acc < 0) {
for (int i = l; i <= r; ++i) {
acc /= A[i];
if (A[i] < 0) {
break;
}
}
}

return max(max_prod, acc);
}

int maxProduct(int A[], int n) {
return helper(A, 0, n - 1);
}``````

• Nice Code, with O(n) space in worst case.

• Neat.
But is there some code missing? I can't see the "divide out the elements from right till the first negative element" part.

• This case is already covered by the first loop.

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