Problem
Given an integer arraynums, find the contiguous subarray with the largest product and return that product.
Example(s)
Consider the following example to understand the expected input and output.Input
nums = [2,3,-2,4]Output
6Explanation
Maximum product subarray = [2,3]
2 * 3 = 6
Solution
This problem can be solved optimally using a Dynamic Programming approach.Unlike the Maximum Subarray problem, multiplication makes the problem more complex because a negative number can turn the smallest product into the largest product.
For each element, we maintain two values:
maxProduct, the maximum product ending at the current position, and minProduct, the minimum product ending at the current position. We need to maintain both because multiplying a negative number by the current minimum product can produce the new maximum product. Similarly, multiplying a negative number by the current maximum product can produce the new minimum product.
For each element, we calculate the maximum and minimum possible products by considering the current element alone, extending the previous maximum product, or extending the previous minimum product.
We also maintain
result, which stores the largest product found so far.
public int maxProduct(int[] nums) {
int maxProduct = nums[0];
int minProduct = nums[0];
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
// Store previous values before updating them.
int previousMax = maxProduct;
int previousMin = minProduct;
// Calculate the maximum and minimum products ending at i.
maxProduct = Math.max(
nums[i],
Math.max(previousMax * nums[i], previousMin * nums[i])
);
minProduct = Math.min(
nums[i],
Math.min(previousMax * nums[i], previousMin * nums[i])
);
// Update the overall maximum product.
result = Math.max(result, maxProduct);
}
return result;
}
Complexity
Each element is processed exactly once, resulting inO(n) time complexity. Only a few variables are used, requiring O(1) extra space.
