152. Maximum Product Subarray

Medium (LinkedIn)

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

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

public class Solution {

// test case:
// nums is empty

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int[] maxValue = new int[len];
    int[] minValue = new int[len];
    maxValue[0] = minValue[0] = nums[0];
    int globalMax = nums[0];

    for(int i = 1; i < len; i++) {
        if(nums[i] > 0) {
            maxValue[i] = Math.max(nums[i], maxValue[i - 1] * nums[i]);
            minValue[i] = Math.min(nums[i], minValue[i - 1] * nums[i]);
        } else {
            maxValue[i] = Math.max(nums[i], minValue[i - 1] * nums[i]);
            minValue[i] = Math.min(nums[i], maxValue[i - 1] * nums[i]);
        }

        globalMax = Math.max(globalMax, maxValue[i]);
    }

    return globalMax;
}

}

Follow up:

reduce space complexity to O(1)

public class Solution {

// test case:
// nums is empty

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int globalMax = nums[0];
    int curMax = nums[0], curMin = nums[0];
    int prevMax = nums[0], prevMin = nums[0];

    for(int i = 1; i < nums.length; i++) {
        if(nums[i] > 0) {
            curMax = Math.max(nums[i], prevMax * nums[i]);
            curMin = Math.min(nums[i], prevMin * nums[i]);
        } else {
            curMax = Math.max(nums[i], prevMin * nums[i]);
            curMin = Math.min(nums[i], prevMax * nums[i]);
        }

        prevMax = curMax;
        prevMin = curMin;
        globalMax = Math.max(globalMax, curMax);
    }

    return globalMax;
}

}