Maximum Subarray Product

Let, an array be like this.

When the array has only positive elements then the product of all elements will be answer. Problem becomes interesting and complex simultaneously when there are negative elements. The way I looked at this problem is as follows.You have three choices to make at any position in array.

1. You can get maximum product by multiplying the current element with maximum product calculated so far.
2. You can get maximum product by multiplying the current element with minimum product calculated so far.
3. Current element might be a starting position for maximum product sub array.

So you have to maintain current maximum product and current minimum product.

curr_max_prod = A[0];
prev_max_prod = A[0];
prev_min_prod = A[0];
ans = A[0];
for i=1 to n-1
{
	curr_max_prod = MAX ( prev_max_prod*A[i], prev_min_prod*A[i], A[i] );
	curr_min_prod = MIN ( prev_max_prod*A[i], prev_min_prod*A[i], A[i] ); 
	Ans = MAX(ans, curr_max_prod); 
	prev_max_prod = curr_max_prod; 
	prev_min_prod = curr_min_prod;
}
return ans;

Above algorithm requires $O(n)$ time and constant space, very similar to Kadane’s algorithm. Collected from Quora and Slightly Edited.