# http://www.geeksforgeeks.org/maximum-product-subarray/
def max_product(input):
max_ending = 1
min_ending = 1
max_so_far = 1
for i in input:
if i > 0:
max_ending = max_ending * i
min_ending = min(min_ending*i, 1)
elif i == 0:
max_ending = 1
min_ending = 1
else:
t = max_ending
max_ending = max(min_ending*i, 1)
min_ending = t * i
if max_so_far < max_ending:
max_so_far = max_ending
return max_so_far
if __name__ == '__main__':
input = [-6,-3,8,-9,-1,-1,3,6,9,0,3,-1]
print(max_product(input))