Given a list of integers, we want to find a subarray with maximum product.
Example:
[1,-2,4,2,-2] Ans: 32
[5,3,1,-2, 0, -4,10,-10]. Ans: 400
Solution:
Here we need to track of minimum product and max product and we ask our selves if it is better of to take:
- just the number at the given index or
- the product of the number at the given index with the min prod or
- the product of the number at the given index with the max prod
Don’t forget to save the prev min value in a temp variable to avoid overwritten by the new min
public int MaxProduct(int[] nums) {
if(nums.Length == 1 )
return nums[0];
int min = nums[0], max= nums[0];
int maxProd = max;
for(int i=1 ;i < nums.Length; i++)
{
int temp = min;
min = Math.Min(Math.Min(temp * nums[i], max * nums[i]), nums[i]);
max = Math.Max(Math.Max(temp * nums[i], max * nums[i]), nums[i]);
maxProd = Math.Max(max, maxProd);
}
return maxProd;