class Solution:

# @param A, a list of non-zero integers

# @return an integer

def maxProductWithoutZero(self, A):

# Two base cases for this recursive method.

if len(A) == 0: return 0

if len(A) == 1: return A[0]

negativeCount = len([i for i in A if i < 0])

if negativeCount % 2 == 0:

# There are even number of negative integers. The product of all them

# is a positive integer as the maximum product among all subarrays.

return reduce(lambda x, y: x * y, A, 1)

else:

# There are odd number of negative integers. We divide the array into

# two subarray: one without the first negative integer, and the other

# without the last negative integer.

firstNeg = 0

while firstNeg < len(A):

if A[firstNeg] < 0: break

firstNeg += 1

lastNeg = len(A) - 1

while lastNeg >= 0:

if A[lastNeg] < 0: break

lastNeg -= 1

return max(self.maxProductWithoutZero(A[:lastNeg]),

self.maxProductWithoutZero(A[firstNeg + 1:]))

# @param A, a list of integers

# @return an integer

def maxProduct(self, A):

begin, end = 0, 0

if A.count(0) != 0: maxProd = 0

else: maxProd = A[0]

# Use 0 (zero) as delimiter to split the original array into small ones,

# which do not contain 0.

while end < len(A):

if A[end] != 0:

end += 1

else:

maxProd = max(maxProd, self.maxProductWithoutZero(A[begin : end]))

end += 1

begin = end

return max(maxProd, self.maxProductWithoutZero(A[begin : end]))