Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example:

Given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Solution:

This question is an extension of Maximum Subarray. However, the production is bit tricky when compared with sum. Assume we have two numbers a=30 and an unknown b, the product of a and b is not necessarily larger than a. If b is negative, the product of a and b becomes small, and if b is zero, the product of a and b is zero. Therefore, we need to prepare two variables: min and max to store the different product.

Code:

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int result = nums[0];
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > 0) {
                max = Math.max(max * nums[i], nums[i]);
                min = Math.min(min * nums[i], nums[i]);
            } else if (nums[i] < 0) {
                int lastMax = max;
                max = Math.max(min * nums[i], nums[i]);
                min = Math.min(lastMax * nums[i], nums[i]);
            } else {
                max = 0;
                min = 0;
            }
            result = Math.max(result, max);
        }
        return result;
    }
}