Maximum Product Subarray

Problem:

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.

Analysis:

2/26/2018 update:
Similar to Maximum subarray. Since the array may contain negative number, we need to keep track of minSoFar and maxSoFar. If current number is negative, we swap min and max.

Solution:

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0)
            return Integer.MIN_VALUE;
        int min = nums[0], max = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = min;
                min = max;
                max = temp;
            }

            min = Math.min(nums[i], min * nums[i]);
            max = Math.max(nums[i], max * nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}

因为是乘法，有正负。如果用加法的方法做，那么[-1,3,4,-2]这种test case就过不了。在当前点记录最大值的同时需要记录最小值。