Maximum Product Subarray

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.

Reduction Transition Function

Product subarray is different from sum subarray in that:

  • A negative number * a negative number produce a big positive number
  • A negative number * a positive number produce a small negative number
  • Thus to get the localMax[i + 1], we may need to know the localMin[i]
  • So we want to record the locaMax and localMin at each step.

Thus we have the following RTF:

  • if nums[i + 1] >= 0:
    • localMax[i + 1] = Math.max(localMax[i] * nums[i + 1], nums[i]);
    • localMin[i + 1] = Math.min(localMin[i] * nums[i + 1], nums[i]);
  • if nums[i + 1] < 0:
    • localMax[i + 1] = Math.max(localMin[i] * nums[i + 1], nums[i]);
    • localMin[i + 1] = Math.min(localMax[i] * nums[i + 1], nums[i]);

The following diagram illustrates the algorithm:

Max product subarray - Page 1.png

Implementation

The following is the implementation of the algorithm:

public int maxProduct(int[] nums) {
    int localMax = nums[0];
    int localMin = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] >= 0) {
            localMax = Math.max(nums[i], nums[i] * localMax);
            localMin = Math.min(nums[i], nums[i] * localMin);
        } else if (nums[i] < 0) {
            int localMaxTemp = Math.max(nums[i], nums[i] * localMin);
            localMin = Math.min(nums[i], nums[i] * localMax);
            localMax = localMaxTemp;
        }

        max = Math.max(localMax, max);
    }
    return max;
}
  • Runtime: O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s