Comment on page
Maximum Product Subarray
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
本题其实是Maximum Subarray Sum问题的延伸，不同的是这里需要考虑元素的符号。
DP的四要素
- 状态：
max_product[i]: 以nums[i]结尾的max subarray productmin_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]的最大值
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 modified 3yr ago