[Leetcode Solution] Maximum Product Subarray

Analysis 

• First idea came in mind is dynamic programming which would be fine if it is required to calculate the maximum sum subarray. However after short thinking it's easy to find out this is a greedy algorithm 
• Assume there is no Zero in the array, we can divide the problem into two sub problems
• If the number of negative elements in the array is even, the maximum product is multiple all the elements together
• If the number of negative elements in the array is odd, we calculate the two products of elements in which the first is from left to the last negative element and the second is from the first negative element to the last element. Then return the bigger one.
• Take zero element into consideration. If we multiple zero into product, the result is always equals to zero. So the solution is divide original array into multiple subarrays delimited by the zero. Then calculate the maximum product within each sub array. Last return the biggest one.

Note

Divide an array by given delimiter and perform calculation on each sub array. Code Template can be found here 
http://fmarss.blogspot.com/2014/10/divide-array-into-sub-arrays.html 

Code