Maximum Product Subarray

Question

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.

Tags

LinkedIn Dynamic Programming Subarray

Related Problems

Medium Best Time to Buy and Sell Stock 41 % Medium Maximum Subarray Difference 23 % Easy Minimum Subarray 38 % Medium Maximum Subarray II

Analysis

本题其实是Maximum Subarray Sum问题的延伸，不同的是这里需要考虑元素的符号。

DP的四要素

• 状态：

  • max_product[i]: 以nums[i]结尾的max subarray product

  • min_product[i]: 以nums[i]结尾的min subarray product

• 方程：

  • max_product[i] = getMax(max_product[i-1] * nums[i], min_product[i-1] * nums[i], nums[i])

  • min_product[i] = getMin(max_product[i-1] * nums[i], min_product[i-1] * nums[i], nums[i])

• 初始化：

  • max_product[0] = min_product[0] = nums[0]

• 结果：

  • 每次循环中 max_product[i] 的最大值

Solution

DP, with O(n) space, O(n) time

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {

        int[] max = new int[nums.length]; // maximum product ending with nums[i]
        int[] min = new int[nums.length]; // minimum product ending with nums[i]

        max[0] = min[0] = nums[0];

        int result = max[0];

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

        return result;
    }
}

DP - Simplified - O(n) space, O(1) time

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] maxProduct = new int[n]; // max subarray product ending in nums[i]
        int[] minProduct = new int[n]; // min subarray product ending in nums[i]

        maxProduct[0] = nums[0];
        minProduct[0] = nums[0];
        int max = maxProduct[0];
        for (int i = 1; i < n; i++) {
            maxProduct[i] = Math.max(nums[i], Math.max(maxProduct[i - 1] * nums[i], minProduct[i - 1] * nums[i]));
            minProduct[i] = Math.min(nums[i], Math.min(maxProduct[i - 1] * nums[i], minProduct[i - 1] * nums[i]));
            max = Math.max(maxProduct[i], max);
        }
        return max;
    }
}

DP, improved, with O(1) space, O(n) time

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
        int result, currentMax, currentMin;
        result = currentMax = currentMin = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int temp = currentMax;
            currentMax = Math.max(nums[i], Math.max(currentMax * nums[i], currentMin * nums[i]));
            currentMin = Math.min(nums[i], Math.min(temp * nums[i], currentMin * nums[i]));

            result = Math.max(currentMax, result);
        }

        return result;
    }
}

O(1) space, O(n) time

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int maxPre = nums[0], minPre = nums[0], max = nums[0], maxHere, minHere;
        for (int i = 1; i < nums.length; i++){
            maxHere = Math.max(nums[i], Math.max(nums[i] * maxPre, nums[i] * minPre));
            minHere = Math.min(nums[i], Math.min(nums[i] * maxPre, nums[i] * minPre));
            max = Math.max(max, maxHere);
            maxPre = maxHere;
            minPre = minHere;
        }
        return max;
    }
}

Same idea but a more concise implementation

int maxProduct(int A[], int n) {
    // store the result that is the max we have found so far
    int r = A[0];

    // imax/imin stores the max/min product of
    // subarray that ends with the current number A[i]
    for (int i = 1, imax = r, imin = r; i < n; i++) {
        // multiplied by a negative makes big number smaller, small number bigger
        // so we redefine the extremums by swapping them
        if (A[i] < 0)
            swap(imax, imin);

        // max/min product for the current number is either the current number itself
        // or the max/min by the previous number times the current one
        imax = max(A[i], imax * A[i]);
        imin = min(A[i], imin * A[i]);

        // the newly computed max value is a candidate for our global result
        r = max(r, imax);
    }
    return r;
}

Reference

• programcreek: Maximum Product Subarray

• Jiuzhang

• LeeCode Discussion