Maximum Product Sub array [ Microsoft – Amazon ]

Problem : Given an array that contains both positive and negative integers, find the product of the maximum product subarray.


Discussion: It is a Similiar problem to maximum sum sub array problem.
Notice,maximum product can also be obtained by minimum (negative) product ending with the last element multiplied by this element.
we use mn_end_here(can be either a negative value or 1) and mx_end_here(can be either a positive value or 1)
So when we find a positive value we update the mx_end_here(multiply).
when we find a negative value mx_end_here will be either 1(as it cant be a negative value)
or multiplied value of mn_end_here with the new negative value.
and mn_end_here will be mx_end_here multiplied by new value(positive value multiplied by negative value will become a negative value.)


Comments are closed.