Maximum Product Subarray.

Consider example:

Input Array = [2, -5, -2, -4, 3]
Maximum product = 24
Input Array = [0, 2]
Maximum product = 2
Input Array = [6, -3, -10, 0, 2]
Maximum product = 180

The way problem can be approached is as follows:

If all numbers are positive than the max product will be product of all numbers. It becomes tricky an array has mix of positive and negative numbers. While iterating through the array we maintain max and min product.

• If the current number is positive then the max product will be Math.max(max*num, num) . We do Math.max, to handle cases when max is 0. At the same time, keep track of minProduct.
• If the current number is negative then max product will be Math.max(min*num, num).

public class MaxProduct {

	public static void main(String[] args) {
		System.out.println(maxProduct(new int[] { -2, 0 }));
		System.out.println(maxProduct(new int[] { 0, 2 }));
		System.out.println(maxProduct(new int[] { 2, -5, -2, -4, 3 }));
	}

	public static int maxProduct(int[] nums) {
		if (nums.length == 1)
			return nums[0];
		int maxProduct = 1;
		int minProduct = 1;
		int maxSoFar = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] >= 0) {
				maxProduct = Math.max(maxProduct * nums[i], nums[i]);
				minProduct = Math.min(minProduct * nums[i], nums[i]);
			} else {
				int temp = maxProduct;
				maxProduct = Math.max(minProduct * nums[i], nums[i]);
				minProduct = Math.min(temp * nums[i], nums[i]);
			}
			if (maxSoFar < maxProduct) {
				maxSoFar = maxProduct;
			}
		}
		return maxSoFar;
	}
}
Output:
0
2
24