Maximum Product Subarray

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

Example

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

Solution: The result can be produced by positive multiply positive or nagetive multiply negative. So we need to track the minimum value for second condition. The state function is similar in maximum subarray.

public int maxProduct(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;
    }
    int[] max = new int[nums.length];
    int[] min = new int[nums.length];
    int res = nums[0];
    max[0] = nums[0];
    min[0] = nums[0];
    for(int i = 1; i < nums.length; i++) {
        if(nums[i] > 0) {
            max[i] = Math.max(max[i - 1] * nums[i], nums[i]);
            min[i] = Math.min(min[i - 1] * nums[i], nums[i]);
        }
        else {
            max[i] = Math.max(min[i - 1] * nums[i], nums[i]);
            min[i] = Math.min(max[i - 1] * nums[i], nums[i]);
        }
        res = Math.max(res, max[i]);
    }
    return res;
}