152. Maximum Product Subarray (Medium)

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.

Solution 1: DP O(n); O(1)

    /**
     * DP O(n);O(1)
     * 1.the max cumulative product UP TO current element starting from SOMEWHERE in the past,
     * and the minimum cumulative product UP TO current element.
     * 2.if we see a negative number, the "candidate" for max should instead become the previous min product,
     * because a bigger number multiplied by negative becomes smaller, hence the swap()
     * 3.at each new element, u could either add the new element to the existing product,
     * or start fresh the product from current index (wipe out previous results), hence the 2 Math.max() lines.
     */
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int max = nums[0];
        int iMax = nums[0];
        int iMin = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = iMax;
                iMax = iMin;
                iMin = temp;
            }
            iMax = Math.max(iMax * nums[i], nums[i]);
            iMin = Math.min(iMin * nums[i], nums[i]);
            max = Math.max(max, iMax);
        }
        return max;
    }

Solution 2: DP O(n); O(n)

    public int maxProduct(int[] nums) {
        int[] max = new int[nums.length];
        int[] min = new int[nums.length];

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

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

        return result;
    }