Algorithm:
1. When the array has only the positive numbers then the answer is simply the product of all of them.
2. In case of negative numbers, we have to adopt a different approach.
3. In case if the current element is positive, then the maximum product can be calculated by multiplying the current number with the maximum product calculated till now.
4. In case if the number is negative then maximum product can be obtained by multiplying the current number with the minimum product calculated so far.
5. For maximum product subArray, the current element may be a starting position.
Implementation:
//Implementation:
int max3(int a, int b, int c)
{
return a > b ? (a > c ? a : c) : (b > c ? b : c);
}
int min3(int a, int b, int c)
{
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}
int maxProductSubArray(int arr[], int len)
{
if(len == 0)
return 0;
if(len == 1)
return arr[0];
int prevMax = arr[0], prevMin = arr[0];
int maxProduct = arr[0];
for(int i = 1; i < len; i++)
{
int currentMax = max3(prevMax * arr[i], prevMin * arr[i], arr[i]);
int currentMin = min3(prevMax * arr[i], prevMin * arr[i], arr[i]);
maxProduct = max(maxProduct, currentMax);
prevMax = currentMax;
prevMin = currentMin;
}
return maxProduct;
}
//Complexity: O(n)
Complexity: O(n)