# 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

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

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;
}``````

Last updated